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

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

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

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

Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 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

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

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

Код

Успешно	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)

Код

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

- как Шарп:

Код

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

(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

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

-- Число делителей:
 
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

-- список простых чисел
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

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

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 сек на интах. Я выше цифры писал. И дело не в сравнительной мощности компов, а в том, что рекурсивных котов с аккумуляторами на ленивых языках надо либо компилить с оптимизациями, либо явно форсить аккумуляторы, а не запускать в интерпретаторе как есть и измерять время в этом режиме. Хотя повторюсь, на данном входящем потоке ваш алгоритм выигрывает.

@Zaresh 0 / 0 / 0 Регистрация: 25.02.2016 Сообщений: 11
		1
	Каково первое треугольное число, у которого более пятисот делителей? 07.10.2016, 23:29. Показов 6528. Ответов 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 Модератор 36578 / 20308 / 4218 Регистрация: 12.02.2012 Сообщений: 33,607 Записей в блоге: 13
	08.10.2016, 10:24	2
	Построить список (бесконечный) треугольных чисел, а потом найти первое, у которого более 500 делителей. Боюсь, долго будет работать... 0

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

@Catstail Модератор 36578 / 20308 / 4218 Регистрация: 12.02.2012 Сообщений: 33,607 Записей в блоге: 13
	08.10.2016, 16:21	7
	Параметр k - это число делителей. Вызывать нужно так: task 100 1 1. Пятьсот, боюсь, hugs98 не вытянет 0

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

@Catstail Модератор 36578 / 20308 / 4218 Регистрация: 12.02.2012 Сообщений: 33,607 Записей в блоге: 13
	08.10.2016, 17:51	9
	Я немного ошибся. Запускать нужно так: task n 1 0 Кстати, у 28 четыре делителя 1

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

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	08.10.2016, 18:47	12
	Сообщение от Artur87 Правильно ли я понял Нет. Сообщение от vrm2 Будет намного быстрее, если число раскладывать на простые множители и уже на основе них считать количество делителей Вряд ли намного. Потому что если число не раскладывается на простые множители (само уже простое), то все равно бежать до корня, как и в предложенном алгоритме. Если же число не простое, то его факторизация выполнится быстрее, но придется потом из списка простых делителей формировать полный список всех делителей. 0

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

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	09.10.2016, 22:16	16
	Сообщение от vrm2 4,8 сек 1.6 сек на интеджерах и 0.3 сек на интах. Я выше цифры писал. И дело не в сравнительной мощности компов, а в том, что рекурсивных котов с аккумуляторами на ленивых языках надо либо компилить с оптимизациями, либо явно форсить аккумуляторы, а не запускать в интерпретаторе как есть и измерять время в этом режиме. Хотя повторюсь, на данном входящем потоке ваш алгоритм выигрывает. 0

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

Решение