Найти все пары натуральных дружественных чисел, меньших 50000.

@sisi11 · Регистрация: 09.02.2018

Студворк — интернет-сервис помощи студентам

Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого (само другое число в качестве делителя не рассматривается). Найти все пары натуральных дружественных чисел, меньших 50000.

@renat_dmitriev · 21.09.2018, 15:10

В чем именно затруднение? Если в алгоритме, то есть специальный раздел форума по алгоритмам.

@klopp · 22.09.2018, 15:40

JavaScript
1
2
3
4
5
6
7
8
const getFriendlyNumbers = (max) => {
    const getSumDivis = (num) => new Array(parseInt(num / 2)).fill(0).reduce((sum, el, i) => sum += !(num % (i + 1)) ? i + 1 : 0, 0);  
    let res = [];
    let arr = new Array(max).fill(0).map((el, i) => getSumDivis(i));
    arr.forEach((el, i) => {if(i == arr[arr[i]] && arr[i] != i) res.push([i, arr[i]]);});
    return res.filter((el, i) => !(i & 1));
}
console.log(getFriendlyNumbers(50000));

@renat_dmitriev · 23.09.2018, 00:06

klopp, Во-первых у вас судя по всему в делители включена единица, что наверное все-таки неверно, хотя я не уверен, во вторых ваш перебор в лоб даже на скромных 50000 работает 10 секунд, на 100000 система может просто лечь.

Добавлено через 4 часа 24 минуты
Оптимизированный по скорости вариант, 50000 находит моментально, за приемлемое время(10 секунд) находит пары для 10 миллионов.

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
function friends(max) {
    
    var res = []
    var allNumbers = {'1': 0};
    var allNumbersTiny = null, limit = 100, tinyLimit = 0; //Для оптимизации поиска
 
    var numbers = allNumbers;
 
    for(simple = 2; simple <= max / 2; simple++) {
 
        if(simple in allNumbers) continue;
 
        if(simple >= limit) {
 
            // После 100 создаем мини-массив, поскольку цикл по ключам объекта
            // работает слишком долго, а нам чем дальше, тем более маленькие числа
            // будут нужны для перебора
 
            var tinyLimitNew = Math.floor((max + 100) / simple);
            if(!allNumbersTiny) {
                allNumbersTiny = {};
                for(var i = 1; i <= tinyLimitNew; i++) allNumbersTiny[i] = allNumbers[i];
 
                numbers = allNumbersTiny;
            } else {
                for(var i = tinyLimitNew + 1; i <= tinyLimit; i++) delete allNumbersTiny[i];
            }
 
            tinyLimit = tinyLimitNew;
            limit += 100;
        }
 
        for(k in numbers) {
 
            var product = k * simple;
            if(product > max) break;
 
            var prevSum = numbers[k], currSum = prevSum, prevProduct = +k;
            var currPow = simple;
 
            while(product <= max) {
 
                if(k == 1) {
                    currSum += currPow === simple ? 0 : prevProduct;
                }  else {
                    currSum += prevProduct + currPow + currPow * prevSum;
                }
                prevProduct = product;
 
                allNumbers[product] = currSum;
                if(allNumbers[currSum] === product) res.push([product, currSum]);
 
                if(product <= tinyLimit) allNumbersTiny[product] = currSum;
 
                currPow *= simple;
                product *= simple;
            }
        }
    }
 
    console.log(res);
}
 
friends(50000);

@klopp · 23.09.2018, 12:36

Сообщение от renat_dmitriev

в делители включена единица

Да, ибо, судя по результатам Пифагора и более поздних авторов, единица входит в сумму делителей
Ваш код очень быстрый, но результаты неверные, вы их проверяли?
Ваши:
0: (2) [75, 48]
1: (2) [1925, 1050]
2: (2) [195, 140]
3: (2) [2024, 2295]
4: (2) [20735, 9504]
5: (2) [16587, 8892]
6: (2) [1648, 1575]
7: (2) [6128, 5775]
Должно быть:
0: (2) [220, 284]
1: (2) [1184, 1210]
2: (2) [2620, 2924]
3: (2) [5020, 5564]
4: (2) [6232, 6368]
5: (2) [10744, 10856]
6: (2) [12285, 14595]
7: (2) [17296, 18416]
М.б. это из-за той самой единицы.
Чуть медленнее вашего(210ms vs 178ms):

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const getFriendlyNumbers = (max) => {
    if(isNaN(max)) return null;
    const getSumDivis = (num) => {
        if(num < 4) return 1;
        let sum = [];
        for(let i = 2, N = Math.sqrt(num); i <= N; i++){
            let tmp = num / i;
            if(tmp == (tmp ^ 0)){
                if(!sum.includes(i)){
                    sum.push(tmp);
                    sum.push(i);
                }
            }   
        }
        return sum.reduce((p,el) => p += el, 1) ;
    }
    let res = [], arr = [];
    for(let i = 0; i <= max; i++)
        arr[i] = getSumDivis(i);
    for(let i = 0; i < arr.length; i++){
        if(i == arr[arr[i]] && i != arr[i])
            res.push([i, arr[i]]);
    }
    return res.filter((el, i) => !(i & 1));
}
console.log(getFriendlyNumbers(50000));

а вот на миллионе разница уже ощутимая 11сек против 1.5сек

@renat_dmitriev · 23.09.2018, 15:03

klopp, Да, это из-за единицы, сделал опционально, по умолчанию включая единицу

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
function summands(max, include1 = true) {
 
    var res = []
    var allNumbers = {'1': +include1};
    var allNumbersTiny = null, limit = 100, tinyLimit = 0; //Для оптимизации поиска
 
    var numbers = allNumbers;
 
    for(simple = 2; simple <= max / 2; simple++) {
 
        if(simple in allNumbers) continue;
 
        if(simple >= limit) {
 
            // После 100 создаем мини-массив, поскольку цикл по ключам объекта
            // работает слишком долго, а нам чем дальше, тем более маленькие числа
            // будут нужны для перебора
 
            var tinyLimitNew = Math.floor((max + 100) / simple);
            if(!allNumbersTiny) {
                allNumbersTiny = {};
                for(var i = 1; i <= tinyLimitNew; i++) allNumbersTiny[i] = allNumbers[i];
 
                numbers = allNumbersTiny;
            } else {
                for(var i = tinyLimitNew + 1; i <= tinyLimit; i++) delete allNumbersTiny[i];
            }
 
            tinyLimit = tinyLimitNew;
            limit += 100;
        }
 
        for(k in numbers) {
 
            var product = k * simple;
            if(product > max) break;
 
            var prevSum = numbers[k] - include1, currSum = prevSum, prevProduct = +k;
            var currPow = simple, sum;
 
            while(product <= max) {
 
                if(k == 1) {
                    currSum += currPow === simple ? 0 : prevProduct;
                }  else {
                    currSum += prevProduct + currPow + currPow * prevSum;
                }
                prevProduct = product;
                
                sum = currSum + +include1;
 
                allNumbers[product] = sum;
                if(sum !== product && allNumbers[sum] === product) res.push([product, sum]);
 
                if(product <= tinyLimit) allNumbersTiny[product] = sum;
 
                currPow *= simple;
                product *= simple;
            }
        }
    }
 
    console.log(res);
}
 
summands(500);

Добавлено через 1 час 52 минуты

Сообщение от klopp

а вот на миллионе разница уже ощутимая 11сек против 1.5сек

Это происходит оттого, что хоть вы и оптимизировали поиск множителей для каждого конкретного числа, но зависимость все еще геометрическая. Мой алгоритм не ищет делители для каждого числа, а идет с обратной стороны - он берет последовательно простые числа и составляет из них прочие, перемножая все степени простого числа на все числа, рассчитанные ранее и по несложной формуле получая сумму делителей. Поэтому с увеличением max зависимость арифметическая.

Единственная проблема была, что строчка for(k in numbers) , которая для каждого просто числа перебирает рассчитанные ранее числа, при большом количестве элементов работает очень долго, даже если после первой итерации будет break, на десятках тысяч записей инициализация итерируемого массива занимает несколько миллисекунд, поэтому пришлось добавить код, создающий уменьшенную копию основного хэша чисел, где будет сначала 500 элементов, и который будет постепенно уменьшаться, так как понятно что при max = 50000 простые числа больше 100 могут быть умножены только на числа меньшие 500.

Фактически весь этот алгоритм - наверное почти что образец поиска делителей для большого диапазона чисел, непосредственно к задаче относится только строчка

JavaScript
1
if(sum !== product && allNumbers[sum] === product) res.push([product, sum]);

@outoftime · 25.09.2018, 04:42

sisi11, klopp, renat_dmitriev, дорогие братья и сёстры, обратите внимание на качество написанного вами кода. Все мы знаем что оптимизация - дело хорошее, но дело вот в чём: оптимизировать можно вечность, ибо нету ничего совершенного помимо идеи. Только идея о вещи может быть совершенной, но никак не сама вещь.

Заканчиваю философствовать. Есть
$ node --version
v9.11.1
на нём будем тестировать код на скорость следующим образом

run.js

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
const klopp = require('./klopp').test;
const renat = require('./renat').test;
const tftm  = require('./tftm').test;
 
timeIt(klopp, 50000, 'klopp');
timeIt(renat, 50000, 'renat');
timeIt(tftm,  50000, 'tftm');
 
function timeIt(test, n, name) {
    console.time(name);
    console.log(test(n));
    console.timeEnd(name);
}

Код уважаемых klopp и renat_dmitriev будем экспортировать в виде функции test и поместим их в файлы klopp.js и renat.js соответственно.

klopp.js

Кликните здесь для просмотра всего текста

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const getFriendlyNumbers = (max) => {
    if(isNaN(max)) return null;
    const getSumDivis = (num) => {
        if(num < 4) return 1;
        let sum = [];
        for(let i = 2, N = Math.sqrt(num); i <= N; i++){
            let tmp = num / i;
            if(tmp == (tmp ^ 0)){
                if(!sum.includes(i)){
                    sum.push(tmp);
                    sum.push(i);
                }
            }   
        }
        return sum.reduce((p,el) => p += el, 1) ;
    }
    let res = [], arr = [];
    for(let i = 0; i <= max; i++)
        arr[i] = getSumDivis(i);
    for(let i = 0; i < arr.length; i++){
        if(i == arr[arr[i]] && i != arr[i])
            res.push([i, arr[i]]);
    }
    return res.filter((el, i) => !(i & 1));
}
 
exports.test = getFriendlyNumbers;

renat.js

Кликните здесь для просмотра всего текста

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function summands(max, include1 = true) {
 
    var res = []
    var allNumbers = {'1': +include1};
    var allNumbersTiny = null, limit = 100, tinyLimit = 0; //Для оптимизации поиска
 
    var numbers = allNumbers;
 
    for(simple = 2; simple <= max / 2; simple++) {
 
        if(simple in allNumbers) continue;
 
        if(simple >= limit) {
 
            // После 100 создаем мини-массив, поскольку цикл по ключам объекта
            // работает слишком долго, а нам чем дальше, тем более маленькие числа
            // будут нужны для перебора
 
            var tinyLimitNew = Math.floor((max + 100) / simple);
            if(!allNumbersTiny) {
                allNumbersTiny = {};
                for(var i = 1; i <= tinyLimitNew; i++) allNumbersTiny[i] = allNumbers[i];
 
                numbers = allNumbersTiny;
            } else {
                for(var i = tinyLimitNew + 1; i <= tinyLimit; i++) delete allNumbersTiny[i];
            }
 
            tinyLimit = tinyLimitNew;
            limit += 100;
        }
 
        for(k in numbers) {
 
            var product = k * simple;
            if(product > max) break;
 
            var prevSum = numbers[k] - include1, currSum = prevSum, prevProduct = +k;
            var currPow = simple, sum;
 
            while(product <= max) {
 
                if(k == 1) {
                    currSum += currPow === simple ? 0 : prevProduct;
                }  else {
                    currSum += prevProduct + currPow + currPow * prevSum;
                }
                prevProduct = product;
                
                sum = currSum + +include1;
 
                allNumbers[product] = sum;
                if(sum !== product && allNumbers[sum] === product) res.push([product, sum]);
 
                if(product <= tinyLimit) allNumbersTiny[product] = sum;
 
                currPow *= simple;
                product *= simple;
            }
        }
    }
 
    for (let i in res)
        res[i].sort();
 
    res.sort(function(x, y) { return x[0] > y[0] });
 
    return res;
}
 
exports.test = summands;

Да, ещё добавим свою поделку, пусть это будет tftm.js

Кликните здесь для просмотра всего текста

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function sumOfFactors(a) {
    let res = 0, factor = 2;
    for (; factor*factor < a; ++factor)
        if (a % factor == 0)
            res += factor + a/factor;
    if (factor*factor == a)
        res += factor;
    return res + 1;
}
 
function test(n) {
    let res = [];
    for (let i = 1; i <= n; ++i) {
        let j = sumOfFactors(i);
        if (i < j && sumOfFactors(j) == i)
            res.push([i, j]);
    }
    return res;
}
 
exports.test = test;

И запустим уже наше тестирование скорости:

Кликните здесь для просмотра всего текста

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$ node run.js 
[ [ 220, 284 ],
  [ 1184, 1210 ],
  [ 2620, 2924 ],
  [ 5020, 5564 ],
  [ 6232, 6368 ],
  [ 10744, 10856 ],
  [ 12285, 14595 ],
  [ 17296, 18416 ] ]
klopp: 219.153ms
[ [ 220, 284 ],
  [ 1184, 1210 ],
  [ 2620, 2924 ],
  [ 5020, 5564 ],
  [ 6232, 6368 ],
  [ 10744, 10856 ],
  [ 12285, 14595 ],
  [ 17296, 18416 ] ]
renat: 112.746ms
[ [ 220, 284 ],
  [ 1184, 1210 ],
  [ 2620, 2924 ],
  [ 5020, 5564 ],
  [ 6232, 6368 ],
  [ 10744, 10856 ],
  [ 12285, 14595 ],
  [ 17296, 18416 ] ]
tftm: 247.590ms

И тут вы можете сказать мол "Да у Рената скорость в 2.5 раза выше, зачем ты вообще код писал?" Отвечать я на этот вопрос не собираюсь, просто попрошу вас разобраться и понять как работают все 3 тестируемые функции из файлов приведённых выше. Советую начинать с лёгкого и переходить к более сложному, для этого вот небольшая подсказка в виде размера файлов в байтах:

$ ls -lh klopp.js renat.js tftm.js
<useless> 789 <useless> klopp.js
<useless> 2223 <useless> renat.js
<useless> 411 <useless> tftm.js

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

@renat_dmitriev · 25.09.2018, 11:07

outoftime, Если мы ограничиваемся 50000, то вы абсолютно правы. Разница в 100 миллисекунд абсолютно несущественна и простота кода приоритетна. Но как я описывал выше, подобный подход перебора чисел и нахождения их множителей дает геометрическую прогрессию при увеличении числа. Мой же алгоритм перемножения простых чисел дает арифметическую прогрессию, поскольку для нахождения суммы множителей для чисел 100 и 1000000 делается одинаковое количество операций. Поэтому как гласит народная мудрость нет смысла сравнивать ж-пу с пальцем, ж-пу надо сравнивать с ж-пой, а палец с пальцем.

@outoftime · 25.09.2018, 22:13

renat_dmitriev, Вы когда за хлебом идёте всё время частный самолёт нанимаете?

@renat_dmitriev · 25.09.2018, 22:53

outoftime,

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@sisi11 2 / 2 / 0 Регистрация: 09.02.2018 Сообщений: 140

	Найти все пары натуральных дружественных чисел, меньших 50000. 21.09.2018, 12:13. Показов 7308. Ответов 9 Метки нет (Все метки) Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого (само другое число в качестве делителя не рассматривается). Найти все пары натуральных дружественных чисел, меньших 50000. 0

@renat_dmitriev 392 / 294 / 121 Регистрация: 26.08.2016 Сообщений: 902
	21.09.2018, 15:10
	В чем именно затруднение? Если в алгоритме, то есть специальный раздел форума по алгоритмам. 0

@renat_dmitriev 392 / 294 / 121 Регистрация: 26.08.2016 Сообщений: 902
	25.09.2018, 11:07
	outoftime, Если мы ограничиваемся 50000, то вы абсолютно правы. Разница в 100 миллисекунд абсолютно несущественна и простота кода приоритетна. Но как я описывал выше, подобный подход перебора чисел и нахождения их множителей дает геометрическую прогрессию при увеличении числа. Мой же алгоритм перемножения простых чисел дает арифметическую прогрессию, поскольку для нахождения суммы множителей для чисел 100 и 1000000 делается одинаковое количество операций. Поэтому как гласит народная мудрость нет смысла сравнивать ж-пу с пальцем, ж-пу надо сравнивать с ж-пой, а палец с пальцем. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	25.09.2018, 22:13
	renat_dmitriev, Вы когда за хлебом идёте всё время частный самолёт нанимаете? 0

@renat_dmitriev 392 / 294 / 121 Регистрация: 26.08.2016 Сообщений: 902
	25.09.2018, 22:53
	outoftime, Не по теме: Дайте пожалуйста ссылку на мой комментарий, где я просил вас читать мне лекции и нотации. Если такого комментария не существует, то давайте пожалуйста будет чуть более уважительны друг к другу и избавим форум от бессмысленного флуда. 0

Найти все пары натуральных дружественных чисел, меньших 50000.

Решение