Каково первое треугольное число, у которого более пятисот делителей?

@Zaresh · Регистрация: 25.02.2016

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

Помогите, пожалуйста, с кодом. Решаю такую задачу

Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число будет 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Перечислим делители первых семи треугольных чисел:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
Как мы видим, 28 - первое треугольное число, у которого более пяти делителей.
Каково первое треугольное число, у которого более пятисот делителей?

Есть решение данной задачи в шарпе Определить первое треугольное число, у которого более пятисот делителей
Там мне запись алгоритма понятна. Что такое треугольное число и как его находить википедия подсказала
А вот с хаскелем впервые столкнулся. Неожиданно оказалось, что в нем нет циклов. Вот мучаюсь, понимаю, что надо как-то применить рекурсию, но не знаю как.
Дальше этого не пошло:
takewhile (n>500)
cons
| условие 1
| условие 2

@Catstail · 08.10.2016, 10:24

Построить список (бесконечный) треугольных чисел, а потом найти первое, у которого более 500 делителей. Боюсь, долго будет работать...

@_Ivana · 08.10.2016, 11:40

Haskell
1
2
3
4
5
divs n = go 1 where
    go i | i*i >  n = 0
         | i*i == n = 1
         | n`mod`i == 0 = 2 + go (i+1)
         | otherwise = go (i+1)

И это не используя факт треугольности числа.

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

Боюсь, долго будет работать...

Code
1
2
3
Успешно  time: 1.66 memory: 4720 signal:0
76576500 has 576 dividers:
[1,2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,20,21,22,25,26,28,30,33,34,35,36,39,42,44,45,50,51,52,55,60,63,65,66,68,70,75,77,78,84,85,90,91,99,100,102,105,110,117,119,125,126,130,132,140,143,150,153,154,156,165,170,175,180,182,187,195,198,204,210,220,221,225,231,234,238,250,252,255,260,273,275,286,300,306,308,315,325,330,340,350,357,364,374,375,385,390,396,420,425,429,442,450,455,462,468,476,495,500,510,525,546,550,561,572,585,595,612,630,650,660,663,693,700,714,715,748,750,765,770,780,819,825,850,858,875,884,900,910,924,935,975,990,1001,1020,1050,1071,1092,1100,1105,1122,1125,1155,1170,1190,1260,1275,1287,1300,1309,1326,1365,1375,1386,1428,1430,1500,1530,1540,1547,1575,1625,1638,1650,1683,1700,1716,1750,1785,1820,1870,1925,1950,1980,1989,2002,2100,2125,2142,2145,2210,2244,2250,2275,2310,2340,2380,2431,2475,2550,2574,2618,2625,2652,2730,2750,2772,2805,2860,2925,2975,3003,3060,3094,3150,3250,3276,3300,3315,3366,3465,3500,3570,3575,3740,3825,3850,3900,3927,3978,4004,4095,4125,4250,4284,4290,4420,4500,4550,4620,4641,4675,4862,4875,4950,5005,5100,5148,5236,5250,5355,5460,5500,5525,5610,5775,5850,5950,6006,6188,6300,6375,6435,6500,6545,6630,6732,6825,6930,7140,7150,7293,7650,7700,7735,7854,7875,7956,8190,8250,8415,8500,8580,8925,9009,9100,9282,9350,9625,9724,9750,9900,9945,10010,10500,10710,10725,11050,11220,11375,11550,11700,11781,11900,12012,12155,12375,12750,12870,13090,13260,13650,13860,13923,14025,14300,14586,14625,14875,15015,15300,15470,15708,15750,16380,16500,16575,16830,17017,17325,17850,17875,18018,18564,18700,19125,19250,19500,19635,19890,20020,20475,21420,21450,21879,22100,22750,23100,23205,23375,23562,24310,24750,25025,25500,25740,26180,26775,27300,27625,27846,28050,28875,29172,29250,29750,30030,30940,31500,32175,32725,33150,33660,34034,34125,34650,35700,35750,36036,36465,38250,38500,38675,39270,39780,40950,42075,42900,43758,44625,45045,45500,46410,46750,47124,48620,49500,49725,50050,51051,53550,53625,55250,55692,56100,57750,58500,58905,59500,60060,60775,64350,65450,66300,68068,68250,69300,69615,70125,71500,72930,75075,76500,77350,78540,81900,82875,84150,85085,86625,87516,89250,90090,92820,93500,98175,99450,100100,102102,102375,107100,107250,109395,110500,115500,116025,117810,121550,125125,128700,130900,133875,136500,139230,140250,145860,150150,153153,154700,160875,163625,165750,168300,170170,173250,178500,180180,182325,193375,196350,198900,204204,204750,210375,214500,218790,225225,232050,235620,243100,248625,250250,255255,267750,278460,280500,294525,300300,303875,306306,321750,327250,331500,340340,346500,348075,364650,375375,386750,392700,409500,420750,425425,437580,450450,464100,490875,497250,500500,510510,535500,546975,580125,589050,607750,612612,643500,654500,696150,729300,750750,765765,773500,841500,850850,900900,911625,981750,994500,1021020,1093950,1126125,1160250,1178100,1215500,1276275,1392300,1472625,1501500,1531530,1701700,1740375,1823250,1963500,2127125,2187900,2252250,2320500,2552550,2734875,2945250,3063060,3480750,3646500,3828825,4254250,4504500,5105100,5469750,5890500,6381375,6961500,7657650,8508500,10939500,12762750,15315300,19144125,25525500,38288250,76576500]

Добавлено через 18 минут

Haskell
1
go (1::Int)

Code
1
2
3
Успешно  time: 0.32 memory: 4708 signal:0
76576500 has 576 dividers:
[1,2,3,4,5..............

- как Шарп:

Code
1
absolute running time: 0,3 sec, cpu time: 0,31 sec, average memory usage: 19 Mb, average nr of threads: 5

Добавлено через 26 минут
UPD: Liscript (версия с рекурсивным эвалюатором) - 40 секунд

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defn task (n k) cond (>= 500 (divs k)) (task (+ 1 n) (+ k n 1)) k)
 
(defn divs (n)
    (defn go (i a)
        cond (> (* i i) n) a
             (= (* i i) n) (+ 1 a)
             (= 0 (mod n i)) (go (+ 1 i) (+ 2 a))
             (go (+ 1 i) a))
    (go 1 0))
 
(task 1 1)

Вечером после катка проверю итеративный эвалюатор, но скорее всего там будет еще медленнее.

@Artur87 · 08.10.2016, 12:37

_Ivana, спасибо! Правильно ли я понял синтаксис haskell, который вы привели:

Haskell
1
2
3
4
5
divs n = go 1 where
    go i | i*i >  n = 0
         | i*i == n = 1
         | n`mod`i == 0 = 2 + go (i+1)
         | otherwise = go (i+1)

n - количество делителей
divs n = go 1 where - начинаем цикл, n:=0, i:=1
go i
i*i > n = 0 - первое условие - делителей нет
i*i == n = 1 - число единица, поэтому делитель только один - тоже единица
n`mod`i == 0 = 2 + go (i+1) - делится нацело, число делителей увеличивается на два ("делители ходят парой")
otherwise = go (i+1) - число делителей не меняем

То есть таким образом решается первая подзадача - найти делители.
Далее надо объявить функцию, которой в качестве аргумента передать divs n. Как я понимаю, надо решить квадратное уравнение вида 2*t(n) = n*(n+1). где t - треугольное число. n = (sqrt (1+8*t(n)) -1) /2
Следовательно, если дробная часть n равна нулю, то t - треугольное, иначе - не треугольное. Такую проверку организовать для n=500.

Код на Лиспе смутно понимаю. Помогите, пожалуйста, переложить его на язык haskell

@Catstail · 08.10.2016, 15:14

Вот мое решение:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
-- Число делителей:
 
numDiv ::Integer -> Int
numDiv n = length $ filter (== 0) $ map (n `mod`) [2,3..n `div` 2]
 
-- Функциональное решение
 
task k =  take 1 $ filter (\ x -> (numDiv x) > k) $ scanl (+) 0 [1,2..]
 
-- Рекурсивное решение
 
task k n p | (numDiv n) > k = n
           | otherwise      = task k (n+p) (p+1)

Но для 500 делителей долго...

@Artur87 · 08.10.2016, 16:01

Catstail, спасибо! А как вы выводите результат? Я работаю в hugs98. Ввожу main > task 1 500 1, где k=1, p=1 - это начальные значения, n=500
Выводит ответ 500
Оставил рекурсивный способ

@Catstail · 08.10.2016, 16:21

Параметр k - это число делителей. Вызывать нужно так: task 100 1 1. Пятьсот, боюсь, hugs98 не вытянет

@Artur87 · 08.10.2016, 16:23

Проверил на примере task 5 1 1 - он выдал 56. Должно быть 28...

@Catstail · 08.10.2016, 17:51

Я немного ошибся. Запускать нужно так: task n 1 0
Кстати, у 28 четыре делителя

@Zaresh · 08.10.2016, 17:56 **[ТС]**

Благодарю всех за помощь! Теперь есть хотя бы пример, буду разбираться, как это все работает ))

@vrm2 · 08.10.2016, 18:21

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

Haskell
1
2
3
4
5
6
7
8
9
-- список простых чисел
primes = ...
 
-- список простых множителей числа n
factors n = ...
 
-- количество делителей
div_count 1 = 1
div_count n = product $ map (+1) $ map length $ group $ sort $ factors n

@_Ivana · 08.10.2016, 18:47

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

Правильно ли я понял

Нет.

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

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

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

@vrm2 · 08.10.2016, 19:31

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

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

Зная простые множители легко посчитать количество делителей, не перебирая каждый делитель. Это делается за O(K), где K - количество простых множителей в числе. В отличии от перебора всех делителей за O(N). Количество простых множителей многократно меньше самого числа, это и дает значительное ускорение.

Поэтому с простыми множителями работа будет не просто быстрее, а быстрее на порядки

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import Data.List (group, sort)
 
-- список простых
primes = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (\p -> p^2 <= i) primes]]
 
-- простые множители числа n
factors 1 = [1]
factors n = factors_ n primes
  where factors_ 1 _ = []
        factors_ n (p:ps) | mod n p == 0 = p : factors_ (div n p) (p:ps)
                          | otherwise    = factors_ n ps
 
-- количество делителей
div_count n = product $ map (+1) $ map length $ group $ sort $ factors n
 
-- треугольные числа
triangles = scanl (+) 1 [2..]
 
main = print $ head $ filter (\t -> div_count t > 500) triangles

@_Ivana · 08.10.2016, 23:49

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

ЗЫ попробовал того же лиспового кота на итеративном эвалюаторе - 4 минуты...

@vrm2 · 09.10.2016, 11:26

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

да, если во входящем потоке преобладают числа, раскладывающеся на множители, то такой алгоритм эффективнее

У нас как раз такой случай. Перевел Ваше решение на Haskell (c "рекурсивным эвалюатором")

Haskell
1
2
3
4
5
6
7
8
9
10
11
task n k | divs k < 500 = task (n+1) (n+k+1)
         | otherwise    = k
 
divs n = go 1 0
  where
    go i a | i*i > n      = a
           | i*i == n     = a+1
           | mod n i == 0 = go (i+1) (a+2)
           | otherwise    = go (i+1) a
 
main = print $ task 1 1

Оно в 30 раз медленнее в сравнении с приведенным выше вариантом.
4,8 сек (перебор делителей) против 0,15 сек. (подсчет делителей по простым множителям)

@_Ivana · 09.10.2016, 22:16

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

4,8 сек

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

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@Zaresh 0 / 0 / 0 Регистрация: 25.02.2016 Сообщений: 11

	Каково первое треугольное число, у которого более пятисот делителей? 07.10.2016, 23:29. Показов 7003. Ответов 15 Метки нет (Все метки) Помогите, пожалуйста, с кодом. Решаю такую задачу Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число будет 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Перечислим делители первых семи треугольных чисел: 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 Как мы видим, 28 - первое треугольное число, у которого более пяти делителей. Каково первое треугольное число, у которого более пятисот делителей? Есть решение данной задачи в шарпе Определить первое треугольное число, у которого более пятисот делителей Там мне запись алгоритма понятна. Что такое треугольное число и как его находить википедия подсказала А вот с хаскелем впервые столкнулся. Неожиданно оказалось, что в нем нет циклов. Вот мучаюсь, понимаю, что надо как-то применить рекурсию, но не знаю как. Дальше этого не пошло: takewhile (n>500) cons \| условие 1 \| условие 2 0

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,741 Записей в блоге: 14
	08.10.2016, 10:24
	Построить список (бесконечный) треугольных чисел, а потом найти первое, у которого более 500 делителей. Боюсь, долго будет работать... 0

@Artur87 1 / 1 / 0 Регистрация: 06.10.2016 Сообщений: 25
	08.10.2016, 16:01
	Catstail, спасибо! А как вы выводите результат? Я работаю в hugs98. Ввожу main > task 1 500 1, где k=1, p=1 - это начальные значения, n=500 Выводит ответ 500 Оставил рекурсивный способ 0

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,741 Записей в блоге: 14
	08.10.2016, 16:21
	Параметр k - это число делителей. Вызывать нужно так: task 100 1 1. Пятьсот, боюсь, hugs98 не вытянет 0

@Artur87 1 / 1 / 0 Регистрация: 06.10.2016 Сообщений: 25
	08.10.2016, 16:23
	Проверил на примере task 5 1 1 - он выдал 56. Должно быть 28... 0

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,741 Записей в блоге: 14
	08.10.2016, 17:51
	Я немного ошибся. Запускать нужно так: task n 1 0 Кстати, у 28 четыре делителя 1

@Zaresh 0 / 0 / 0 Регистрация: 25.02.2016 Сообщений: 11
	08.10.2016, 17:56 [ТС]
	Благодарю всех за помощь! Теперь есть хотя бы пример, буду разбираться, как это все работает )) 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	08.10.2016, 23:49
	vrm2, да, если во входящем потоке преобладают числа, раскладывающеся на множители, то такой алгоритм эффективнее, и чем больше в среднем множителей у элемента потока, тем более явно это проявляется. ЗЫ попробовал того же лиспового кота на итеративном эвалюаторе - 4 минуты... 0

Каково первое треугольное число, у которого более пятисот делителей?

Решение