Как найти дружные числа

В этом уроке мы узнаем, как найти дружественные числа в Python. Во-первых, разберемся, что это такое и как их можно использовать.

Дружественные числа – это два разных числа, связанных таким образом, что сумма собственного делителя каждого из них равна другому числу.

Другими словами, сумма всех собственных делителей x и сумма всех собственных делителей y должна быть равна противоположному числу.

 
sum_x = y and sum_y = x 

Предположим, у нас есть два числа, 123 и 426, нам нужно найти все правильные делители 123 и 426; затем мы суммируем собственный делитель 123 и то же самое с 426.

Сумма собственного делителя 123 равна 426, а собственного делителя 426 – 123.

Ниже приведены шаги, чтобы определить, являются ли два числа дружественными или нет:

• Сначала возьмите два целых числа в качестве входных данных от пользователя.
• Получите правильный делитель обоих чисел и просуммируйте их.
• Теперь проверьте, совпадает ли данное число с противоположным числом.
• Если они равны, то они дружелюбны.
• Получаем результат.

Программа:

 
x=int(input('Enter first number : ')) 
y=int(input('Enter second number : ')) 
sum1=0 
sum2=0 
for i in range(1,x): 
    if x%i==0: 
        sum1+=i 
for j in range(1,y): 
    if y%j==0: 
        sum2+=j 
if(sum1==y and sum2==x): 
    print('Given numbers are Amicable!') 
else: 
    print('Given numbers are not Amicable!') 

Выход:

Enter first number : 220 
Enter second number : 284 
Given numbers are Amicable!     

Посмотрим еще один вывод:

Enter first number : 365 
Enter second number : 456 
Given numbers are not Amicable!  

Объяснение:

В приведенном выше примере мы берем вводимые пользователем данные и сохраняем их в отдельных переменных. Мы использовали оператор for loop и if, чтобы найти правильный делитель обоих чисел. Затем мы находим сумму собственных делителей обоих чисел. Используя оператор if, мы проверили, равна ли сумма собственного делителя чисел другому числу и наоборот.

Как узнать количество пар дружественных чисел из списка

У нас есть два списка целых чисел, где мы выберем каждое число из обоих списков и сравним их. Если числа дружественные, увеличьте счет и вернитесь. Давайте разберемся в следующем примере.

Пример:

 
# Python3 program to count 
# amicable pairs in an array 
# Calculate the sum 
# of proper divisors 
def sumOfDiv(x): 
    sum = 1 
    for i in range(2, x): 
        if x % i == 0: 
            sum += i 
    return sum 
# Check if pair is amicable 
def CheckAmicable(a, b): 
    if sumOfDiv(a) == b and sumOfDiv(b) == a: 
        return True 
    else: 
        return False 
def countPairs(arr, n): 
    count = 0 
    for i in range(0, n): 
        for j in range(i + 1, n): 
            if CheckAmicable(arr[i], arr[j]): 
                count = count + 1 
    return count 
list1 = [220, 284, 1184, 
        1210, 2, 5] 
n1 = len(list1) 
print(countPairs(list1, n1)) 
 
list2 = [2620, 2924, 5020, 
        5564, 6232, 6368] 
n2 = len(list2) 
print(countPairs(list2, n2)) 

Выход:

2 
3  

Это простой способ узнать количество дружественных пар чисел. Мы проходим и проверяем, составляют ли они дружескую пару.

From Wikipedia, the free encyclopedia

Amicable numbers are two different natural numbers related in such a way that the sum of the proper divisors of each is equal to the other number. That is, s(a)=b and s(b)=a, where s(n)=σ(n)-n is equal to the sum of positive divisors of n except n itself (see also divisor function).

The smallest pair of amicable numbers is (220, 284). They are amicable because the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71 and 142, of which the sum is 220. (A proper divisor of a number is a positive factor of that number other than the number itself. For example, the proper divisors of 6 are 1, 2, and 3.)

The first ten amicable pairs are: (220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), (10744, 10856), (12285, 14595), (17296, 18416), (63020, 76084), and (66928, 66992). (sequence A259180 in the OEIS). (Also see OEIS: A002025 and OEIS: A002046) It is unknown if there are infinitely many pairs of amicable numbers.

A pair of amicable numbers constitutes an aliquot sequence of period 2. A related concept is that of a perfect number, which is a number that equals the sum of its own proper divisors, in other words a number which forms an aliquot sequence of period 1. Numbers that are members of an aliquot sequence with period greater than 2 are known as sociable numbers.

History[edit]

Amicable numbers were known to the Pythagoreans, who credited them with many mystical properties. A general formula by which some of these numbers could be derived was invented circa 850 by the Iraqi mathematician Thābit ibn Qurra (826–901). Other Arab mathematicians who studied amicable numbers are al-Majriti (died 1007), al-Baghdadi (980–1037), and al-Fārisī (1260–1320). The Iranian mathematician Muhammad Baqir Yazdi (16th century) discovered the pair (9363584, 9437056), though this has often been attributed to Descartes.^[1] Much of the work of Eastern mathematicians in this area has been forgotten.

Thābit ibn Qurra’s formula was rediscovered by Fermat (1601–1665) and Descartes (1596–1650), to whom it is sometimes ascribed, and extended by Euler (1707–1783). It was extended further by Borho in 1972. Fermat and Descartes also rediscovered pairs of amicable numbers known to Arab mathematicians. Euler also discovered dozens of new pairs.^[2] The second smallest pair, (1184, 1210), was discovered in 1867 by 16-year-old B. Nicolò I. Paganini (not to be confused with the composer and violinist), having been overlooked by earlier mathematicians.^[3][4]

The First Ten Amicable Pairs

#	m	n
1	220	284
2	1,184	1,210
3	2,620	2,924
4	5,020	5,564
5	6,232	6,368
6	10,744	10,856
7	12,285	14,595
8	17,296	18,416
9	63,020	76,084
10	66,928	66,992

By 1946 there were 390 known pairs, but the advent of computers has allowed the discovery of many thousands since then. Exhaustive searches have been carried out to find all pairs less than a given bound, this bound being extended from 10⁸ in 1970, to 10¹⁰ in 1986, 10¹¹ in 1993, 10¹⁷ in 2015, and to 10¹⁸ in 2016.

As of 27 April 2023, there are over 1,227,820,104 known amicable pairs.^[5]

Rules for generation[edit]

While these rules do generate some pairs of amicable numbers, many other pairs are known, so these rules are by no means comprehensive.

In particular, the two rules below produce only even amicable pairs, so they are of no interest for the open problem of finding amicable pairs coprime to 210 = 2·3·5·7, while over 1000 pairs coprime to 30 = 2·3·5 are known [García, Pedersen & te Riele (2003), Sándor & Crstici (2004)].

Thābit ibn Qurra theorem[edit]

The Thābit ibn Qurra theorem is a method for discovering amicable numbers invented in the ninth century by the Arab mathematician Thābit ibn Qurra.^[6]

It states that if

p = 3×2^{n − 1} − 1,

q = 3×2ⁿ − 1,

r = 9×2^{2n − 1} − 1,

where n > 1 is an integer and p, q, and r are prime numbers, then 2ⁿ×p×q and 2ⁿ×r are a pair of amicable numbers. This formula gives the pairs (220, 284) for n = 2, (17296, 18416) for n = 4, and (9363584, 9437056) for n = 7, but no other such pairs are known. Numbers of the form 3×2ⁿ − 1 are known as Thabit numbers. In order for Ibn Qurra’s formula to produce an amicable pair, two consecutive Thabit numbers must be prime; this severely restricts the possible values of n.

To establish the theorem, Thâbit ibn Qurra proved nine lemmas divided into two groups. The first three lemmas deal with the determination of the aliquot parts of a natural integer. The second group of lemmas deals more specifically with the formation of perfect, abundant and deficient numbers.^[6]

Euler’s rule[edit]

Euler’s rule is a generalization of the Thâbit ibn Qurra theorem. It states that if

p = (2^{n − m} + 1)×2^m − 1,

q = (2^{n − m} + 1)×2ⁿ − 1,

r = (2^{n − m} + 1)²×2^{m + n} − 1,

where n > m > 0 are integers and p, q, and r are prime numbers, then 2ⁿ×p×q and 2ⁿ×r are a pair of amicable numbers. Thābit ibn Qurra’s theorem corresponds to the case m = n − 1. Euler’s rule creates additional amicable pairs for (m,n) = (1,8), (29,40) with no others being known. Euler (1747 & 1750) overall found 58 new pairs increasing the number of pairs that were then known to 61.^[2][7]

Regular pairs[edit]

Let (m, n) be a pair of amicable numbers with m < n, and write m = gM and n = gN where g is the greatest common divisor of m and n. If M and N are both coprime to g and square free then the pair (m, n) is said to be regular (sequence A215491 in the OEIS); otherwise, it is called irregular or exotic. If (m, n) is regular and M and N have i and j prime factors respectively, then (m, n) is said to be of type (i, j).

For example, with (m, n) = (220, 284), the greatest common divisor is 4 and so M = 55 and N = 71. Therefore, (220, 284) is regular of type (2, 1).

Twin amicable pairs[edit]

An amicable pair (m, n) is twin if there are no integers between m and n belonging to any other amicable pair (sequence A273259 in the OEIS).

Other results[edit]

In every known case, the numbers of a pair are either both even or both odd. It is not known whether an even-odd pair of amicable numbers exists, but if it does, the even number must either be a square number or twice one, and the odd number must be a square number. However, amicable numbers where the two members have different smallest prime factors do exist: there are seven such pairs known.^[8] Also, every known pair shares at least one common prime factor. It is not known whether a pair of coprime amicable numbers exists, though if any does, the product of the two must be greater than 10⁶⁷.^{[citation needed]} Also, a pair of coprime amicable numbers cannot be generated by Thabit’s formula (above), nor by any similar formula.

In 1955, Paul Erdős showed that the density of amicable numbers, relative to the positive integers, was 0.^[9]

In 1968, Martin Gardner noted that most even amicable pairs known at his time have sums divisible by 9,^[10] and a rule for characterizing the exceptions (sequence A291550 in the OEIS) was obtained.^[11]

According to the sum of amicable pairs conjecture, as the number of the amicable numbers approaches infinity, the percentage of the sums of the amicable pairs divisible by ten approaches 100% (sequence A291422 in the OEIS). Although all amicable pairs up to 10,000 are even pairs, the proportion of odd amicable pairs increases steadily towards higher numbers, and presumably there are more of them than of even amicable pairs (A360054 in OEIS).

Gaussian amicable pairs exist.^[12]

Generalizations[edit]

Amicable tuples[edit]

Amicable numbers satisfy and which can be written together as . This can be generalized to larger tuples, say , where we require

For example, (1980, 2016, 2556) is an amicable triple (sequence A125490 in the OEIS), and (3270960, 3361680, 3461040, 3834000) is an amicable quadruple (sequence A036471 in the OEIS).

Amicable multisets are defined analogously and generalizes this a bit further (sequence A259307 in the OEIS).

Sociable numbers[edit]

Sociable numbers are the numbers in cyclic lists of numbers (with a length greater than 2) where each number is the sum of the proper divisors of the preceding number. For example, are sociable numbers of order 4.

Searching for sociable numbers[edit]

The aliquot sequence can be represented as a directed graph, , for a given integer , where denotes the
sum of the proper divisors of .^[13]
Cycles in represent sociable numbers within the interval . Two special cases are loops that represent perfect numbers and cycles of length two that represent amicable pairs.

References in popular culture[edit]

• Amicable numbers are featured in the novel The Housekeeper and the Professor by Yōko Ogawa, and in the Japanese film based on it.
• Paul Auster’s collection of short stories entitled True Tales of American Life contains a story (‘Mathematical Aphrodisiac’ by Alex Galt) in which amicable numbers play an important role.
• Amicable numbers are featured briefly in the novel The Stranger House by Reginald Hill.
• Amicable numbers are mentioned in the French novel The Parrot’s Theorem by Denis Guedj.
• Amicable numbers are mentioned in the JRPG Persona 4 Golden.
• Amicable numbers are featured in the visual novel Rewrite.
• Amicable numbers (220, 284) are referenced in episode 13 of the 2017 Korean drama Andante.
• Amicable numbers are featured in the Greek movie The Other Me (2016 film).
• Amicable numbers are discussed in Brian Cleggs book Are Numbers Real?
• Amicable numbers are mentioned in the 2020 novel Apeirogon by Colum McCann.

See also[edit]

• Betrothed numbers (quasi-amicable numbers)
• Amicable triple — Three-number variation of Amicable numbers.

Notes[edit]

References[edit]

•  This article incorporates text from a publication now in the public domain: Chisholm, Hugh, ed. (1911). «Amicable Numbers». Encyclopædia Britannica (11th ed.). Cambridge University Press.
• Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36. ISBN 978-1-4020-2546-4. Zbl 1079.11001.
• Wells, D. (1987). The Penguin Dictionary of Curious and Interesting Numbers. London: Penguin Group. pp. 145–147.
• Weisstein, Eric W. «Amicable Pair». MathWorld.
• Weisstein, Eric W. «Thâbit ibn Kurrah Rule». MathWorld.
• Weisstein, Eric W. «Euler’s Rule». MathWorld.

External links[edit]

• M. García; J.M. Pedersen; H.J.J. te Riele (2003-07-31). «Amicable pairs, a survey» (PDF). Report MAS-R0307.
• Grime, James. «220 and 284 (Amicable Numbers)». Numberphile. Brady Haran. Archived from the original on 2017-07-16. Retrieved 2013-04-02.
• Grime, James. «MegaFavNumbers — The Even Amicable Numbers Conjecture». YouTube. Archived from the original on 2021-11-23. Retrieved 2020-06-09.
• Koutsoukou-Argyraki, Angeliki (4 August 2020). «Amicable Numbers (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)».

Содержание

• Формула для поиска дружественных чисел
• Примеры дружественных чисел
• Как разложить число и найти его делители
• Решенные упражнения
• — Упражнение 1
• Решение
• — Упражнение 2.
• Решение
• Ссылки

Вдружеские или дружественные числа Это два натуральных числа a и b, сумма делителей одного из которых (не включая число) равна другому числу, а сумма делителей этого другого числа (не включая его) равна первому числу.

Было найдено много пар чисел, обладающих этим любопытным свойством. Их не так уж и мало, самые маленькие — 220 и 284, обнаруженные несколько веков назад. Итак, мы собираемся привести их в качестве примера того, что означает эта особенная дружба между числами.

Делителями 220, исключая 220, являются: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110. В свою очередь, делители 284, не включая 284, равны: 1, 2, 4, 71 и 142.

Теперь складываем делители первого числа, которое равно 220:

D₁ = 1+2+4+5+10+11+20+22+44+55+110 = 284

Мы замечаем, что фактически сумма равна 284, дружественному числу.

Затем складываются делители числа 284:

D₂ = 1+2+4+71+142 = 220

И первый член пары получается.

Древнегреческим математикам пифагорейской школы, основанной Пифагором (569–475 гг. До н. Э.), Автором знаменитой одноименной теоремы, удалось обнаружить эту своеобразную взаимосвязь между этими двумя числами, которым они приписывали множество мистических качеств.

Они были также известны исламским математикам средневековья, которым удалось определить общую формулу для нахождения дружественных чисел около 850 года нашей эры.

Формула для поиска дружественных чисел

Исламский математик Табит ибн Курра (826–901) нашел способ генерировать несколько дружественных чисел. Шон п, какие Y р три простых числа, то есть числа, которые допускают только 1 и сами себя в качестве делителей.

Когда выполняется следующее:

р = 3,2^п-1 – 1

q = 3,2^п – 1

г = 9,2^2н-1 – 1

С участием п число больше 1, тогда:

а = 2^пpq и b = 2^пр

Они составляют пару дружественных чисел. Давайте проверим формулу для n = 2 и посмотрим, какую пару дружественных чисел она генерирует:

р = 3,2^2-1 – 1= 3. 2 – 1 = 5

q = 3,2² – 1= 11

г = 9,2^2.2-1 – 1= 71

Так:

а = 2^пpq = 2². 5. 11 = 220

b = 2^пг = 2². 71 = 284

Формула средневекового математика работает для n = 2, поскольку это как раз первые дружественные числа, о которых говорилось вначале и которые были известны уже в средние века.

Однако теорема не работает для всех найденных до сих пор дружественных чисел, только для n = 2, n = 4 и n = 7.

Спустя столетия швейцарский математик Леонард Эйлер (1707-1783) вывел новое правило поиска дружественных чисел, основанное на правилах Табита ибн Курры:

р = (2^н-м + 1). 2^м – 1

q = (2^н-м + 1). 2^п – 1

г = (2^н-м + 1)². 2^{т + п}  – 1

Как всегда, числа p, q и r простые, но теперь есть два целых показателя степени: m и n, из которых m должно удовлетворять следующему условию:

1 ≤ м ≤ п-1

Аналогично формируется пара дружественных чисел:

а = 2^пpq

b = 2^пр

Если m = n-1, теорема Табита получается снова, но, как и в случае с теоремой исламского математика, не все дружественные числа удовлетворяют правилу Эйлера. Однако с ним увеличилось количество известных до того времени дружественных чисел.

Вот первые пары показателей (m, n), с помощью которых можно найти несколько дружественных чисел:

(1,2), (3,4), (6,7), (1,8) и (29,40)

Позже, в разделе упражнений, мы найдем пару дружественных чисел, которая образуется благодаря показателям (3,4) правила Эйлера.

Примеры дружественных чисел

-220 и 284

-1184 и 1210

-2620 и 2924

-5020 и 5564

-6232 и 6368

-10,744 и 10,856

-12 285 и 14 595

-17 296 и 18 416

Конечно, компьютер может сгенерировать гораздо больше дружественных пар чисел.

Как разложить число и найти его делители

Теперь мы посмотрим, как найти делители числа, чтобы проверить, дружат ли они.Согласно определению дружественных чисел, все делители каждого участника необходимы, чтобы их можно было сложить, кроме самих чисел.

Теперь натуральные числа можно разделить на две группы: простые числа и составные числа.

Простые числа допускают только 1 и себя как точные делители. А составные числа, со своей стороны, всегда можно выразить как произведение простых чисел и иметь другие делители, кроме 1 и самих себя.

Любое составное число N, такое как 220 или 284, можно выразить следующим образом:

N = а^п . б^м. c^п … р^k

Где a, b, c… r — простые числа, а n, m, p… k — показатели, принадлежащие натуральным числам, которые могут быть начиная с 1.

В терминах этих показателей существует формула, чтобы узнать, сколько (но не какие) делители имеет число N. Пусть C будет этой величиной:

C = (n +1) (m + 1) (p +1)… (k + 1)

После того, как число N выражено в терминах произведений простых чисел и известно, сколько у него делителей, у нас уже есть инструменты, чтобы узнать, каковы его делители, как простые, так и непростые. И это то, что вам нужно знать их всех, чтобы проверить, являются ли они друзьями, кроме последнего, которым является сам номер.

Решенные упражнения

— Упражнение 1

Найдите все делители пары дружественных чисел 220 и 284.

Решение

Давайте сначала найдем простые делители 220, которое является составным числом:

220 │2
110 │2
55  │5
11  │11
1    │

Разложение 220 на простые множители:

220 = 2 х 2 х 5 х 11 = 2².5. 11

Следовательно, n = 2, m = 1, p = 1 и имеет:

С = (2 + 1). (1 + 1). (1 + 1) = 12 делителей

Первые делители, которые замечаются при разложении числа: 1, 2, 4, 5 Y 11. И они тоже 110 Y 55.

Им не хватило бы 5 из них, которые производят продукты между кузенами и их комбинациями: 2².5 = 20;  2².11 = 44;  2. 11 = 22 и наконец 1 и его собственный 220.

Аналогичная процедура выполняется для 284:

284 │2
142 │2
71 │71
1 │

284 = 2². 71

С = (2 + 1). (1 + 1) = 3 x 2 = 6 делителей

Эти делители: 1, 2, 4, 71, 142 и 284, как указано в начале.

— Упражнение 2.

Проверка формулы Эйлера на n = 4 и m = 3 дает тройку простых чисел (p, q, r) = (23,47, 1151). Какая из них образуется пара дружественных чисел?

Решение

Простые числа p, q и r вычисляются по формуле:

р = (2^н-м + 1). 2^м – 1

q = (2^н-м + 1). 2^п – 1

г = (2^н-м + 1)². 2^{т + п}  – 1

Подставляя значения m = 3 и n = 4, получаем:

р = (2^4-3 + 1). 2³ – 1= 23

q = (2^4-3 + 1). 2⁴ – 1 = 47

г = (2^4-3 + 1)². 2⁴⁺³  – 1 = 1151

Теперь формула применяется для поиска пары дружественных чисел a и b:

а = 2^пpq

b = 2^пр

а = 2^пpq = 16,23,47 = 17,296

b = 2^пг = 16. 1151 = 18,416

И действительно, они входят в список первых пар дружественных чисел, которые мы показали ранее.

Ссылки

1. Балдор, А. 1986. Арифметика. Издания и распространения Кодекса.
2. Все о простых числах. Дружелюбные номера. Получено с: Númeroprimos.org.
3. Wolfram MathWorld. Правило Эйлера. Получено с: mathworld.wolfram.com.
4. Википедия. Дружные номера. Получено с: en.wikipedia.org.
5. Википедия. Дружелюбные номера. Получено с: es.wikipedia.org.

	(Время: 1 сек. Память: 16 Мб Сложность: 25%)
	Будем называть два числа дружными, если они состоят из одних и тех же цифр. Например, числа 1132 и 32321 являются дружными, а 12 и 123 – нет (в первом числе нет цифры 3). Требуется написать программу, которая определит, являются ли два заданных числа дружными.
	Входные данные
	Входной текстовый файл INPUT.TXT содержит в первой строке натуральное число K – количество тестов. Количество тестов не превышает 10. В следующих K строках содержатся по два целых числа A и B, разделенные одним пробелом (0 < A < 109, 0 < B < 109).
	Выходные данные
	Выходной текстовый файл OUTPUT.TXT должен содержать K строк. Для каждого теста в отдельной строке надо выдать сообщение “YES”, если A и B являются дружными, или “NO”, если не являются. В сообщениях кавычки не печатать.
	import math
	def main():
	input_file = open(«input.txt», «r»)
	output_file = open(«output.txt», «w»)
	line = input_file.readline().split(‘ ‘)
	n = int(line[0])
	for i in range(n):
	line = input_file.readline().split(‘ ‘)
	a, b = set(line[0]), set(line[1])
	print(a, b)
	a = sorted(a)
	b = sorted(b)
	if b[0] == ‘n’:
	b.remove(‘n’)
	print(a, b)
	if a == b:
	output_file.write(«YES» + «n»)
	else:
	output_file.write(«NO» + «n»)
	if __name__ == «__main__»:
	main()