Проект Эйлера на Python

Условие: Используйте   names.txt   (правый клик и 'Save Link/Target As...'), текстовый файл размером 46 КБ, содержащий более пяти тысяч имён. Начните с сортировки в алфавитном порядке. Затем подсчитайте алфавитные значения каждого имени и умножьте это значение на порядковый номер имени в отсортированном списке для получения количества очков имени. Например, если список отсортирован по алфавиту, имя COLIN (алфавитное значение которого 3 + 15 + 12 + 9 + 14 = 53) является 938-ым в списке. Поэтому, имя COLIN получает 938 × 53 = 49714 очков. Какова сумма очков имён в файле? Решение Повторяюсь - я не очень люблю "лингвистические" задачи, но эту постараюсь решить.

Пусть d( n ) определяется как сумма делителей  n  (числа меньше  n , делящие  n  нацело). Если d( a ) =  b  и d( b ) =  a , где  a  ≠  b , то  a  и  b  называются дружественной парой, а каждое из чисел  a  и  b  - дружественным числом. Например, делителями числа 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, поэтому d(220) = 284. Делители 284 - 1, 2, 4, 71, 142, поэтому d(284) = 220. Подсчитайте сумму всех дружественных чисел меньше 10000. Решение Для начала определим функцию, которая будет возвращать сумму делителей числа: def get_sum(n):     s=0     for i in range(1,n):         if n%i==0:             s+=i     return s Думаю не требует объяснений все довольно тривиально Далее определяем функцию, возвращающую список дружественных чисел до числа n:   def gen_friendlys(n):     res=[]     for i in range(1,n):         if i not in res:             tmp=get_sum(i)             if i==get_sum(tmp) and i!=tmp:                 res.append(i)                 res.

Условие: Если записать числа от 1 до 5 английскими словами (one, two, three, four, five), то используется 3 + 3 + 5 + 4 + 4 = 19 букв. Сколько букв понадобится для записи всех чисел от 1 до 1000 (one thousand) включительно? Решение Если честно, я не очень люблю "лингвистические" задачи за достаточно сложные условия и минимум размаха для написания красивой логики, но все же возьмусь за эту. 

Условие: Следующая повторяющаяся последовательность определена для множества натуральных чисел: n  →  n /2 ( n  - чётное) n  → 3 n  + 1 ( n  - нечётное) Используя описанное выше правило и начиная с 13, сгенерируется следующая последовательность: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 Получившаяся последовательность (начиная с 13 и заканчивая 1) содержит 10 элементов. Хотя это до сих пор и не доказано (проблема Коллатца (Collatz)), предполагается, что все сгенерированные таким образом последовательности оканчиваются 1. Какой начальный элемент меньше миллиона генерирует самую длинную последовательность? Решение Гипотеза Коллатца сводится к тому что данная последовательность всегда оканчивается единицей. Если верить Википедии, то она не доказана и над проверкой гипотезы на больших числах сейчас трудятся миллионы видеокарт добровольцев вычислительной сети BOINC в рамках проекта Collatz Conjecture. Мы же будем работать с не очень большими числами и банальной рекурсии на

В данной статье речь пойдет сразу о двух достаточно простых задачах из проекта Эйлера Задача 13  Найдите первые десять цифр суммы следующих ста 50-значных чисел. Решение 100 чисел 50-ти знаков -достаточно много текста чтобы помещать его в текст программы, а тем более в текст статьи. Для загрузки списка из файла я создал функцию get_list - построчно читает числа из файла и возвращает список с преобразованными в integer числами. Осталось только применить к полученному списку sum и вывести первых десять цифр, используя прием взятия среза в последней строке программы: def get_list(file,n):     f = open(file, 'r')     lst=[]     for i in range(n):          tmp=f.readline()          lst.append(int(tmp[0:50]))     return lst lst=get_list('C:\\exp\\100rows.txt',100) print(str(sum(lst))[0:10]) Задача 16 Сумма цифр степени 2 15  = 32768, сумма цифр 3 + 2 + 7 + 6 + 8 = 26. Какова сумма цифр числа 2 1000 ? Решение: еще проще задачи 13  Нам по сути

Условие задачи  Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 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 - первое треугольное число, у которого более пяти делителей. Каково первое треугольное число, у которого более пятисот делителей? Решение  Задача состоит из 2-х этапов: - Этап 1. Собственно генерация числа - Этап 2. Поиск делителей или на математическом языке "факторизация числа.

Условие задачи Сумма простых чисел меньше 10 - это 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел меньше двух миллионов. Решение Мы уже использовали алгоритмы поиска простых чисел на python здесь и здесь . Но в этой задаче я хочу попробовать нечто новое - Решето Эратосфена  . Это достаточно интересный и быстрый алгоритм, но я его не использовал в прошлых задачах т.к они не сильно подходили под условия - здесь же решето Эратосфена подходит практически идеально.

Условие задачи: Тройка Пифагора - три натуральных числа  a  <  b  <  c , для которых выполняется равенство a 2  +  b 2  =  c 2 Например, 3 2  + 4 2  = 9 + 16 = 25 = 5 2 . Существует только одна тройка Пифагора, для которой  a  +  b  +  c  = 1000. Найдите произведение  abc . Решение: Первые формулы зависимостей троек Пифагора известны из трудов  Эвклида 2100 г до н.э, самая известная из них:             a   = 2 mn ,   b   =   m 2   −   n 2 ,   c   =   m 2   +   n 2   ,   m   >   n Ну что же, попробуем ее реализовать в коде.

Условие Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9 × 9 × 8 × 9 = 5832. 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 071984038509624554443629812309878

Условие задачи: Сумма квадратов первых десяти натуральных чисел 1 2  + 2 2  + ... + 10 2  = 385 Квадрат суммы первых десяти натуральных чисел (1 + 2 + ... + 10) 2  = 55 2  = 3025 Следовательно, разность между суммой квадратов и квадратом суммы первых десяти натуральных чисел составляет 3025 − 385 = 2640. Найдите разность между суммой квадратов и квадратом суммы первых ста натуральных чисел. Решение: Для оптимизации будем использовать формулу квадрата суммы из школьной арифметики: ( a + b )   2 = a   2 + 2 a b + b   2

Условие задачи     Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число - 13.     Какое число является 10001-ым простым числом?     Принцип ее решения очень похож на Задачу 3 (наибольший простой делитель), но ограничением будет выступать не само число, а количество чисел в словаре.  Решение     Для начала определим функцию определения простого числа: def issimple(n):     r=math.ceil(math.sqrt(n))     for i in range(2,n):         if n%i==0:             return False     return True     Здесь аналогично задаче 3 - для оптимизации перебираем числа до квадратного корня искомого числа. Если n делится на хотя бы одно число от 2-х до корня n возвращаем false. Иначе True Приведу полный оптимизированный текст: import math def issimple(n):     r=math.ceil(math.sqrt(n))     for i in range(2,n):         if n%i==0:             return False     return True n=5 s=[2,3] while True:     if issimple(

Условие задачи 2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10. Какое самое маленькое число  делится нацело  на все числа от 1 до 20? Скажу сразу - не смотря на не большой диапазон чисел условия реализация этой задачи получилась громоздкой и ее выполнение занимает больше всего времени - около 90 с  несмотря на все попытки оптимизации. Решение 

Условие задачи Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел – 9009 = 91 × 99. Найдите самый большой палиндром, полученный умножением двух трёхзначных чисел. Заметка. Обычно перед решением каждой задачи я обращаюсь к математическим формулам для поиска оптимального алгоритма, но данную задачу я решил в лоб без особой математической базы. Работает медленно, но меньше 1-й минуты что удовлетворяет основному принципу решения. Решение

Условие задачи Простые делители числа 13195 - это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143, являющийся простым числом? Решение Простым числом, является натуральное число больше единицы, которое имеет 2 делителя - 1 и само себя.  Для начала найдем все простые делители необходимого числа.  Чтобы сократить поиск будем перебирать до квадратного корня  600851475143 округленного вверх  ( функцией  math.ceil) Перебор будем вести начиная с числа 3. Если i делит число на цело, рекурсивно обращаемся к функции issimple c аргументом i. Функция issimple возвращает пустой список если число является простым. В этом случае число попадает в результирующий список Далее остается только вернуть максимальное значение массива простых чисел, которые нацело делят число 600851475143  Код Python import math def issimple(a): r=math.ceil(math.sqrt(a)) lst=[] for i in range(3,r): if a%i==0: if issimple(i)==[]: lst.app

Задача 2  Четные числа Фибоначчи Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2, первые 10 элементов будут: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Найдите сумму всех четных элементов ряда Фибоначчи, которые не превышают четыре миллиона. Решение на Python Пока не особо владею приемами функционального программирования на Python, но кое-какие шаблонные фитчи использую. Прошу строго не судить о коде: f=[1,2] i=2 a=0 while f[i]<4000000:     f.append(f[i-1]+f[i-2])     i+=1     a=f[i] res=filter(lambda x:x%2==0, f) print(sum(res)) Цикл создающий числа Фибоначчи на основе перебора элементов списка я позаимствовал из Википедии, немного видоизменив под задачу - вместо порога по количеству чисел я установил порог по значению в 4000000. Но данный цикл имеет недостаток- он создает одно число, которое больше установленного порога - 5702887, но оно является не четным и на результат не влияет.  Переменная i х

 . Задача №1 Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел - 23. Найдите сумму всех чисел меньше 1000, кратных 3 или 5. Решение