На этом шаге мы рассмотрим задачи на применение императивного стиля программирования и целочисленной арифметики.

Фрагмент теории

1. Присваивание значений

    Функция SET связывает значение аргумента X с вычисленным значением Y. Синтаксис функции:

    (SET X Y)  ,

    При помощи функции SET с атомом X можно связать значение S-выражения Y. Заметим, что (SET X Y) эквивалентно оператору присваивания X:=Y в языках императивного программирования.

    Обратите внимание на то, что функция SET вычисляет значения обоих аргументов, т.е. с ее помощью можно связать значение Y с именем, которое получается также путем вычисления. Например:

   $ (SET (CAR (A B C)) 25)
   25
   $ A
   25

    Связать символ с его значением можно и с помощью функции SETQ. Эта функция отличается от функции SET тем, что она вычисляет только свой второй аргумент. Об автоматическом блокировании вычисления первого аргумента напоминает буква Q (Quote) в имени функции.

    Таким образом, (SETQ A B) эквивалентно (SET (QUOTE A) B).

2. Организация циклов

    Представителем группы итерационных функций в языке LISP служит функция LOOP, имеющая в общем случае вид:

   (LOOP
       Expr1
       Expr2
        ...
       ExprN
   )

где в качестве аргументов могут быть использованы любые S-выражения либо специальные конструкции вида ( C E₁ E₂ ... E_k ), где C, E₁, E₂, ..., E_k - S-выражения.

    В последнем случае список используется в качестве точки анализа условия окончания цикла. Если вычисление S-выражения C возвращает значение NIL, итерационный процесс продолжается, в противном случае прекращается, но предварительно вычисляются последовательно S-выражения E₁, E₂, ..., E_k и последнее из полученных значений возвращается в качестве значения функции LOOP.

Демонстрационные примеры

   ; ------------------------------------------- ;
   ; Пример императивного стиля программирования ;
   ; ------------------------------------------- ;
   (DEFUN SUM1 (LAMBDA (LST S)
      (SETQ S 0)
      (LOOP
         ; Выход из цикла при опустошении списка ;
         ( (NULL LST) S )
         (SETQ S (+ S (CAR LST)))
         (SETQ LST (CDR LST))
      )
   ))
   ; --------------------------------------------- ;
   ; Пример функционального стиля программирования ;
   ; --------------------------------------------- ;
   (DEFUN SUM (LAMBDA (LST)
      (COND ( (NULL LST) 0 )
            (  T  (+ (CAR LST) (SUM (CDR LST))) )
      )
   ))

   ; ------------------------------------------- ;
   ; Пример императивного стиля программирования ;
   ; ------------------------------------------- ;
   (DEFUN SUMMA (LAMBDA (N)
      (SETQ S 0)
      (SETQ I 1)
      (PRIN1 "Сумма квадратов чисел от 1 до N равна: ")
      ( LOOP
          ; Выход из цикла при N=0 ;
          ( (EQ N 0) 0 )
          ; Выход из цикла при I>N ;
          ( (> I N) S )
          (SETQ S (+ S (* I I)))
          (SETQ I (+ I 1))
      )
   ))

   ; ------------------------------------------- ;
   ; Пример императивного стиля программирования ;
   ; ------------------------------------------- ;
   (DEFUN FACTORIAL (LAMBDA (NUM ANS)
      (SETQ ANS 1)
      (LOOP
         ( (EQ NUM 0) ANS )  ; Выход из цикла при NUM=0 ;
         (SETQ ANS (* NUM ANS))
         (SETQ NUM (- NUM 1))
      )
   ))
   ; --------------------------------------------- ;
   ; Пример функционального стиля программирования ;
   ; --------------------------------------------- ;
   (DEFUN FACT (LAMBDA (X)
      (COND ( (ZEROP X) 1 )
            (  T  (* X (FACT (- X 1))) )
      )
   ))

   ; ------------------------------------------- ;
   ; Пример императивного стиля программирования ;
   ; ------------------------------------------- ;
   (DEFUN POWER (LAMBDA (NUM1 NUM2)
      ( (AND (ZEROP NUM1) (MINUSP NUM2))
            (PRINT "Результат не существует!") )
      (SETQ NUM3 1)
      (LOOP
         (SETQ NUM2 (DIVIDE NUM2 2))
         ( ( (EQ (CDR NUM2) 1)
                        (SETQ NUM3 (* NUM1 NUM3)) ) )
         ( SETQ NUM2 (CAR NUM2) )
         ( (ZEROP NUM2) NUM3 )
         ( SETQ NUM1 (* NUM1 NUM1))
      )
   ))
   ; --------------------------------------------- ;
   ; Пример функционального стиля программирования ;
   ; --------------------------------------------- ;
   (DEFUN EXPT (LAMBDA (NUM1 NUM2)
      (COND ( (ZEROP NUM2) 1 )
            ( (ZEROP (- NUM2 1)) NUM1 )
            (  T  (* NUM1
                         (EXPT NUM1 (- NUM2 1))) )
      )
   ))

   ; ------------------------------------------- ;
   ; Пример императивного стиля программирования ;
   ; ------------------------------------------- ;
   (DEFUN NTH (LAMBDA (LST NUM)
      (LOOP
         (SETQ LST (CDR LST))
         (SETQ NUM (- NUM 1))
         ( (ZEROP NUM) LST )  ; Выход из цикла при NUM=0 ;
      )
   ))
   ; --------------------------------------------- ;
   ; Пример функционального стиля программирования ;
   ; --------------------------------------------- ;
   (DEFUN NTH_1 (LAMBDA (LST NUM)
      (COND ( (ZEROP NUM) LST )
            (  T  (NTH_1 (CDR LST) (- NUM 1)) )
      )
   ))

   ; ------------------------------------------- ;
   ; Пример императивного стиля программирования ;
   ; ------------------------------------------- ;
   (DEFUN GCD (LAMBDA (NUM1 NUM2 NUM3)
      (LOOP
         ( (ZEROP NUM2) NUM1 )
         (SETQ NUM3 NUM2)
         (SETQ NUM2 (MOD NUM1 NUM2))
         (SETQ NUM1 NUM3)
      )
   ))
   ; --------------------------------------------- ;
   ; Пример функционального стиля программирования ;
   ; --------------------------------------------- ;
   (DEFUN GCD_1 (LAMBDA (M N)
   ; Функция представляет формальную запись  алго- ;
   ; ритма, описанного еще Евклидом  (Начала, кни- ;
   ; га 7, теорема 2)                              ;
      (COND ( (EQ M N) M )
            ( (< M N) (GCD_1 N M) )
            (  T  (GCD_1 (- M N) N) )
      )
   ))

   ; ------------------------------------------- ;
   ; Пример императивного стиля программирования ;
   ; ------------------------------------------- ;
   (DEFUN SIMPLE (LAMBDA (N)
      (SETQ FLAG 1)
      (COND ( (AND (EQ (MOD N 2) 0) (NOT (EQ N 2))) PRIN1 "Не простое!" )
            (  T  ( (SETQ I 3)
                    (LOOP
                       ( (< (CAR (DIVIDE  N 2) ) I) )
                       ( (EQ (MOD N I) 0)
                              (SETQ FLAG 0) )
                       ( SETQ I (+ I 2) )
                    )
                    (COND ( (EQ FLAG 0)  PRIN1 "Не простое!" )
                          (   T          PRIN1 "Простое!"    ))
                    )
            )
      )
   ))
   ; --------------------------------------------- ;
   ; Пример функционального стиля программирования ;
   ; --------------------------------------------- ;
   (DEFUN ISPRIM (LAMBDA (N)
      (COND ( (EQ N 1) NIL )
            (    T    (ISPR N 2) )
      )
   ))
   ; --------------------- ;
   (DEFUN ISPR (LAMBDA (N M)
      (COND ( (EQ M N)          T  )
            ( (EQ (MOD N M) 0) NIL )
            (   T (ISPR N (+ M 1)) )
      )
   ))

   (DEFUN STRING-NUM (LAMBDA (X)
   ; Перевод списка цифр в список, содержащий ;
   ;     соответствующие однозначные числа    ;
      (COND ( (NULL X) NIL )
            (  T  (CONS (POSITION (CAR X)
                                  (UNPACK 123456789))
                        (STRING-NUM (CDR X))
                  )
            )
      )
   ))
   ; ---------------------------- ;
   (DEFUN  POSITION (LAMBDA (X LST)
   ; Функция POSITION возвращает положение атома X в  ;
   ; одноуровневом списке LST (первый элемент имеет   ;
   ; номер 1). Если элемента в списке нет, то функция ;
   ;                   возвращает 0                   ;
      (COND ( (NULL LST)       0 )
            ( (EQ X (CAR LST)) 1 )
            ( (MEMBER X LST)
                  (+ 1 (POSITION X (CDR LST))) )
            (  T  0 )
      )
   ))
   ; ----------------------- ;
   (DEFUN NUMBER (LAMBDA (LST)
   ; Дан  числовой  список  LST, содержащий  однозначные ;
   ; числа. "Построить" целое число из элементов данного ;
   ;                          списка                     ;
      (COND ( (NULL LST) 0 )
            (  T  (+ (* (CAR LST)
                               (STEPEN 10
                                       (-
                                         (LENGTH LST) 1))
                        )
                        (NUMBER (CDR LST))
                  )
            )
      )
   ))
   ; ----------------------- ;
   (DEFUN STEPEN (LAMBDA (X A)
   ; Возведение целого числа X в целую ;
   ;    неотрицательную степень A      ;
      (COND ( (ZEROP A) 1 )
            ( (ZEROP (- A 1)) X )
            (  T  (* (STEPEN X (- A 1)) X) )
      )
   ))

Задачи для самостоятельного решения

1. Написать программу, в результате выполнения которой выясняется, входит ли цифра 2 в запись целого числа n.
2. Найти такую тройку последовательных натуральных чисел, сумма квадратов которых равнялась бы сумме квадратов двух следующих за ними натуральных чисел. Вероятно, Вы видели картину художника Н.П.Богданова-Бельского (1868-1945) "Устный счет". На ней изображен урок устного решения задач в школе села Татево, Смоленской области, в школе, которую основал и в которой преподавал Сергей Александрович Рачинский с 70-х годов прошлого века. На картине воспроизведен С.А.Рачинский. Обратите внимание на задачу, записанную на классной доске: (10²+11²+12²+13²+14²)/365. Подсчет показывает, что 10²+11²+12² = 13²+14² = 365.
3. Обращенным числом называется число, записанное теми же цифрами, но в обратном порядке. Например, 3805, обращенное - 5083. Палиндромическим числом называется число, равное обращенному. Например, 121,5995 - палиндромические числа. Написать программу нахождения нескольких палиндромических чисел меньших 10001.
4. Написать программу, возвращающую значение N, если N - простое число, и "ничего не делающую" в противном случае (N-нечетное). Число называется простым, если оно не имеет других делителей, кроме 1 и самого себя.
5. Существует ли такая четверка последовательных натуральных чисел, сумма квадратов которых равна сумме квадратов трех следующих натуральных чисел? (Ответ: 21²+22²+23²+24²=25²+26²+27²)
6. Проверить, делится ли заданное натуральное число на 19, используя следующий признак делимости: число делится на 19 тогда и только тогда, когда число его десятков, сложенное с удвоенным числом единиц, делится на 19.
7. В одной математической книге наборщик вместо чисел 2⁵*9² набрал 2592. Корректор эту серьезную ошибку пропустил, и книга вышла в свет в таком виде. Эту книгу изучало много математиков, все предыдущие и последующие вычисления проверялись, а эту явную ошибку, пропущенную наборщиком и корректором, никто не заметил. Как же это могло случиться? Дело в том, что 2⁵*9² = 2592. Это, по-видимому, единственный в своем роде числовой курьез! Проверьте это.

       Другое решение предложил Алексей Анатольевич Дорофеев из города Ростов-на-Дону, студент механико-математического факультета, специальности "прикладная математика" Ростовского Государственного Университета. Вот его письмо:

       "Я зашел случайно на http://it.kgsu.ru/Lisp/lisp0118.html ; когда читал "Задачи для самостоятельного решения", сразу обратил внимание на задачу № 7....

       Собственно говоря, именно из-за этой задачи я и попал сюда - набрал в поиске "числовые курьезы" (я увлекаюсь математикой и всякого рода курьезами) и зашел по ссылке. Очень интересная задача, должен сказать (самое главное - красивая; до этого я думал, что "красивых курьезов не бывает" - теперь убежден в обратном). Так вот, вернемся к задаче: "Это, по-видимому, единственный в своем роде числовой курьез! Проверьте это." Думал сегодня весь вечер, 4 часа как минимум. Так вот, мой ответ: нет, не единственный. А нашел я вот что: 35721 = (3^5) * 7 * 21. Ну чем не курьез? По-моему, курьезнее курьезного. Честно скажу, нигде я это не читал и не смотрел, а нашел около полчаса назад после как минимум 4 часов глубоких раздумий :)"

       Проверьте истинность решения, предложенного Алексеем Анатольевичем.

      

8. Найти число "счастливых" билетов с номерами от 000000 до 999999 включительно. Билет считается "счастливым", если сумма левых трех цифр номера равна сумме правых трех цифр. Решить задачу перебором всех возможных номеров билетов.
9. Написать программу "переработки" данного целого n >=10 в целое число, запись которого отличается от записи числа n перестановкой первой и последней цифр.
10. Какой цифрой оканчивается число 777⁷⁷⁷ (Ответ: 5)
11. Определить, какой цифрой оканчивается число (...((7⁷)⁷)⁷...)⁷, если известно, что возведение в степень повторяется 77 раз.
12. Докажите, что 999993¹⁹⁹⁹ - 777777¹⁹⁹⁷ кратно 5.
13. Делится ли число 7⁷⁷+1 на 5?
14. Найти последнюю цифру следующих чисел: 6¹⁹⁷¹, 9¹⁹⁷¹, 3¹⁹⁷¹, 2¹⁹⁷¹.
15. Доказать, что разность 9⁵¹²-7⁵¹² делится на 10.
16. Сколько существует целых чисел, меньших 1000, не делящихся ни на 5, ни на 7? Сколько из этих чисел не делится ни на 3, ни на 5, ни на 7? (Ответ: 686; 457)
17. Проверить на нескольких примерах справедливость следующего утверждения: если число р простое и р больше 100, но меньше 200, то число 210-р тоже является простым числом.
18. Найдется ли такое натуральное число n, что число 2ⁿ+15 будет составным? (Ответ: n=7)
19. Число 29 можно записать в виде суммы различных степеней числа 2: 2⁴+2³+2²+1. Запишите в виде суммы различных степеней числа 2 заданное натуральное число.
20. Какой цифрой оканчивается десятичная запись числа 142+142²+142³+...+142²⁰?
21. Известно, что числа n⁴+n³+n²+n не делятся на 10. Какими цифрами может оканчиваться десятичная запись числа n? (Ответ: 1 или 6)
22. Немецкий математик М.Штифель (1487-1567 гг.) утверждал, что числа вида 2²ⁿ⁺¹-1, n принадлежит N, являются простыми. Прав ли он?
23. При каком наименьшем натуральном m делятся на 7 числа вида: 1) m³ + 3^m; 2) m² + 3^m.
24. Определить, сколько среди чисел от 1 до 1000 таких, которые делятся на 4, но не имеют цифры 4 в своей записи? (Ответ: 162)
25. Найти двузначное число, обладающее тем свойством, что куб суммы его цифр равен квадрату самого числа. (Ответ: 27)
26. В каких двузначных числах удвоенная сумма цифр равна их произведению? (Ответ: 63,44,36)
27. Найти двузначное число, равное утроенному произведению его цифр. (Ответ: 15,24)
28. Подряд выписаны целые числа от 1 до 100. Сколько раз в этой записи встречаются цифры: а) нуль, б) единица, в) три.
29. Напишите наименьшее трехзначное число кратное 3 так, чтобы первая цифра его была 6, и все цифры были бы различны.
30. Найти все трехзначные числа, равные сумме факториалов своих цифр.
31. Дописать к 523... три цифры так, чтобы полученное шестизначное число делилось на 7, 8 и на 9.
32. Установить, является ли данное целое число р простым, используя теорему Вильсона (1770 г.): целое число р является простым тогда и только тогда, когда (р-1)! + 1 делится на р. Отметим, что данная теорема была доказана Лагранжем в 1773 г.
33. Укажите такое n, при котором число n⁴+(n+1)⁴ является составным.  (Ответ: 5)
34. Обозначим через M(a,b,c,...,k) наименьшее общее кратное, а через D(a,b,c,...,k) наибольший общий делитель чисел a,b,c,...,k. Написать программу, вычисляющую М(a,b,c) по формуле: М(a,b,c) = a*b*c*D(a,b,c)/(D(a,b)*D(b,c)*D(a,c))
35. Натуральные числа m и n взаимно просты и n<m. Какое число больше: [1*m/n]+[2*m/n]+...+[n*m/n] или [1*n/m]+[2*n/m]+...+[m*n/m] и насколько? (Ответ: первая сумма больше на m-n)
36. Для каждого натурального числа k<=10 найти наименьшее натуральное число n, для которого k*2^{2^n}+1 есть число составное.

              k: 1 2 3 4 5 6 7 8 9 10
    Oтвет: 
              n: 5 1 2 2 1 1 3 1 2  2
    

37. Написать программу нахождения всех натуральных чисел, меньших n, квадрат суммы цифр которых равен m.
38. Можно ли данное целое р представить в виде суммы двух квадратов целых чисел?
39. Написать программу нахождения по данному целому числу n>7 пары целых неотрицательных чисел a и b таких, что n=3a+5b.
40. Гольдбахом было высказано предположение, что каждое четное число, большее или равное 4, представимо в виде суммы двух простых. Это предположение до сих пор не доказано и не опровергнуто. Написать программу проверки этой гипотезы для данного четного числа. Результатом выполнения программы должен быть вывод самого числа, если не удалось найти пару простых слагаемых, и вывод пары соответствующих простых чисел, если таковая пара найдена.
41. Составить программу поиска среди чисел n, n+1, ..., 2n так называемых близнецов, т.е. двух простых чисел, разность которых равна 2.
42. Найдите хотя бы одно решение уравнения a²+b⁴=c⁵ в положительных целых числах. (Ответ: 256, 64, 32)
43. Верно ли, что при любом натуральном n число n³+5n-1 простое? (Ответ: нет, n=6)
44. Найти среднее арифметическое всех делителей данного числа n (включая 1 и n). Проверить, что оно будет заключено между корнем квадратным из n и (n+1)/2.
45. Найти число всех делителей данного натурального числа n. Проверить, что произведение всех делителей равно n^s/2, где s - число всех делителей.
46. Натуральное число называется палиндромическим, если оно читается одинаково с обеих сторон, например, 171. Возьмем любое число. Если оно не палиндром, то перевернем его и сложим с исходным. Если не получился палиндром, то проделаем с ним то же и т.д., пока не получится палиндром. Для всех чисел от 1 до 1000 найти, через сколько шагов получается палиндром и какой.
47. Подсчитать, сколькими нулями оканчивается произведение всех чисел от 1 до 100 включительно. (Ответ: 24)
48. Натуральное число называют совершенным, если оно равно сумме всех своих делителей, не считая его самого (например, 6=1+2+3 - совершенное число). Напишите программу, проверяющую, является ли заданное число совершенным.
49. Написать программу, отыскивающую совершенные числа.
    Примените следующую теорему.
    Теорема Евклида ("Начала", книга 9).
    В тех случаях, когда число p=2ⁿ⁺¹-1 - простое, p*2ⁿ является совершенным.
    Никомах из Герасы указал три первых совершенных числа: 6, 28, 496 .
50. Дружественными числами называется пара чисел, обладающих таким свойством: сумма собственных делителей первого из них равна второму числу, а сумма собственных делителей второго числа равна первому числу.
    Например, сумма делителей числа 220 равна 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284, а сумма делителей числа 220 и 284 - дружественная пара.
    Вторая дружественная пара (1184 и 1210) была найдена в 1867 г. шестнадцатилетним итальянцем Б.Паганини.
    Написать программу для нахождения дружественных чисел, используя способ, указанный еще в IX веке арабским математиком Сабитом ибн Корра.
    Теорема Сабита. Если все три числа p = 3*2^n-1 - 1, q = 3*2ⁿ - 1, r = 9*2^2n-1 - 1 - простые, то числа A = 2ⁿ*p*q и B = 2ⁿ*r - дружественные.
    При n=2 числа p=5, q=11 и p=71 - простые, и получается пара чисел 220 и 284, найденная еще Пифагором. Однако теорема Сабита дает дружественные числа и при других n, например:

                    n=4               n=7
                    А=17296           А=9363584
                    В=18416           В=9437056
    

    В настоящее время известно, что этими тремя случаями исчерпываются все значения n<=20000, при которых указанный способ дает дружественные числа.
51. Решения уравнения a²+b²=c² в целых положительных числах называют пифагоровыми тройками. Например: (3,4,5), (5,12,13), (41,140,149).
    Будем искать простейшие пифагоровы тройки (a,b,c), то есть те, у которых н.о.д.(a,b,c)=1 . Решение этой задачи указал еще Диофант из Александрии (ок.250 г.н.э.): если n и m - два взаимно простых целых (положительных) числа, разность которых n-m положительна и нечетна, то (2*n*m, n² -m², n²+m²) - простейшая пифагорова тройка, и любая из этих троек может быть найдена этим способом.
    Написать программу нахождения нескольких пифагоровых троек, используя теорему Диофанта.
52. Задача Ферма. Найти куб, который в сумме со всеми его собственными делителями дает квадрат (например, сумма числа 343 и всех его собственных делителей 343+49+7+1=400 является квадратом).
53. Задача Ферма. Найти квадрат, который в сумме со всеми его собственными делителями дает куб.
54. Написать программу, вычисляющую число свободных от квадратов чисел, меньших или равных X. Число называется свободным от квадратов, если оно не делится ни на один квадрат простого числа.
55. Найти значения n<=N, обладающие следующим свойством: пятая степень суммы цифр десятичной записи числа n равна n². (Ответ: 1 и 243)
56. При каком минимальном N число вида (9^N-7^N) делится на 10? (Ответ: 512)
57. Составить программу составления таблицы простых чисел, не превосходящих данного целого N, применяя решето Эратосфена.
    Способ состоит в следующем. Выписываем числа 1, 2, ..., N (1) Первое большее единицы число этого ряда есть 2. Оно делится только на 1 и на самого себя и, следовательно, оно простое.
    Вычеркиваем из ряда (1) (как составные) все числа, кратные 2, кроме самого числа 2. Первое следующее за 2 невычеркнутое число есть 3. Оно не делится на два (иначе оно оказалось бы вычеркнутым). Следовательно, 3 делится только на 1 и на самого себя, и потому оно также будет простым. Вычеркиваем из ряда (1) все числа, кратные 3, кроме самого 3. Первое следующее за 3 невычеркнутое число есть 5. Оно не делится ни на 2, ни на 3 (иначе оно оказалось бы вычеркнутым). Следовательно, 5 делится только на 1 и на самого себя, а потому оно также будет простым. И т.д.
    Легко доказать, что составление таблицы простых чисел, не превосходящих N, закончено, как только вычеркнуты все составные кратные простых, не превосходящих квадратного корня из N.
58. Написать программу игры на ЭВМ под названием "быки и коровы". Правила игры чрезвычайно просты. Один из партнеров - ведущий. Он задумывает любое четырехзначное число. Требуется лишь, чтобы ни одна из составляющих это число цифр не повторялось. Задача другого партнера (назовем его просто игроком) - отгадать это число. Игрок называет пробные числа. Игра заканчивается, если названо число, задуманное ведущим. Чем меньше ходов-попыток потребуется для этого игроку, тем лучше он играет. Ведущий помогает игроку подсказками. Что это за подсказки, рассмотрим на примере.
    Предположим, задумано число 9480. Назовем его кодом. Как и предписывается условиями игры, все цифры в коде различны. Игрок называет свое пробное число 7984. Ведущий сравнивает его с кодом 9480. Так как числа не совпадают, то игра не закончена. Ведущий сообщает игроку количество "быков" и "коров", содержащихся в предложенном им пробном числе. "Быками" называют те его цифры, которые по значению и позиции совпадают с соответствующими цифрами задуманного кода. В нашем примере "бык" один - цифра 8. "Коровы" - это цифры, которые совпадают с цифрами задуманного кода, находятся в иных позициях. В числе 7984 "коров" две: 9 и 4. Понятно, что отгадать код или назвать четыре "быка"- это одно и тоже.
59. Написать программу определения соответствующего дня недели по известным целым числам: J - число, М - месяц, А - год, применяя метод М.Ленуара, который заключается в следующем:
    • вычислить величину N: если месяц - январь или февраль високосного года, то N=1; если месяц - январь или февраль обычного года, то N=2; в других случаях N=0.
      Чтобы узнать, является ли год високосным, можно действовать следующим образом:
      • разложить год на две части А1 и А2: А1 содержит 2 старшие цифры года, А2 содержит 2 младшие цифры года;
      • если А2=0 и А1 делится на 4, то год високосный;
      • если А2 не равно 0, то год високосный, если А2 делится на 4;
    • вычислить "код" дня С по формуле С = целое (365.25 * А2) + целое (30.56 * М) + J + N;
    • вычислить остаток S от деления С на 7: если S=0, то день - среда, если S=1, то день - четверг, если S=2, то день - пятница, ..., если S=0, то день - вторник.
60. Написать программу, отыскивающую совершенные числа с использованием теоремы Д.Х.Лемера (1931 г.): число 2^p-1 (где p>2) является простым тогда и только тогда, когда оно делит v_p-1, где v₁=4 и v_n+1=v_n²-2.
    В качестве иллюстрации отметим, что 2³-1 делит  v₂= 14; 2⁴-1 не делит v₃= 194; 2⁵-1 делит v₄=37634.
61. Найти натуральное число от 1 до 10000 с максимальной суммой делителей.
62. Гипотеза Симона о факториале состоит в следующем: только четыре факториала являются произведением трех последовательных целых чисел. Вот два из них: 4!=2*3*4, 5!=4*5*6. Составьте программу, которая помогла бы найти следующее натуральное число, обладающее указанным свойством. Не могли бы Вы опровергнуть гипотезу Симона?

        Задачи 63-81 заимствованы из [1].

       

63. Найти все числа, состоящее из трех различных цифр, каждое из которых делится на квадрат суммы своих цифр. (Ответ: 162, 243, 324, 392, 45, 512, 65, 648, 810, 972)
64. Найти все пятизначные квадраты, у которых сумма чисел, образованных двумя первыми цифрами и двумя последними цифрами, равна точному кубу. (Ответ: 152²=23104; 23+04=27=9³; 237²=56169; 56+69=125=5³; 251²=63001; 63+01=64=4³)
65. Какое число образовано из пяти последовательных цифр (идущих не обязательно по порядку) так, что число, образованное первыми двумя цифрами, умноженное на среднюю цифру, дает число, образованное последними двумя цифрами? (число 01234 считать пятизначным). (Ответ: 3412 = 03412; 03*04=12; 4312 = 04312; 04*03=12; 13452; 13*04=52)
66. У меня есть пять карточек, на которых изображены цифры 1,3,5,7 и 9. Как расположить их в ряд таким образом, чтобы произведение числа, образованного первой парой карточек, на число, образованное последней парой карточек, минус число, стоящее на средней карточке, равнялось числу, составленному из повторений одной и той же цифры (т.е. получится число, в котором все цифры одинаковые).
67. Можете ли Вы расположить цифры 1,2,3,4,5,7,8,9 двумя группами по четыре цифры в каждой так, чтобы суммы чисел, составленных из цифр каждой группы, были равны между собой.
68. Можете ли Вы расположить цифры 1,2,3,4,5,6,7,8 двумя группами по четыре цифры в каждой так, чтобы суммы чисел, составленных из цифр каждой группы, были равны между собой. (Ответ: 1,2,7,8 и 3,4,5,6)
69. Найти все числа, у которых кубический корень совпадает с суммой цифр. Докажите, что значность кубического корня и значность суммы цифр числа совпадают, если число не более, чем шестизначно. (Ответ: 1 = 1³, 1 = 1; 512 = 8³, 5+1+2 = 8; 4913 = 17³, 4+9+1+3 = 17; 5832 = 18³, 5+8+3+2 = 18; 17576 = 26³, 1+7+5+7+6 = 26; 19683 = 27³, 1+9+6+8+3 = 27)
70. Некоторые натуральные числа могут быть представлены в виде суммы кубов целых неотрицательных чисел: например 9=2³+1³, 27=3³+0³. Составить алгоритм, отыскивающий наименьшее натуральное число, имеющее два разных таких представления. (Представления 9=2³+1³ и 9=1³+2³ считаются одинаковыми).
71. Найти наименьшее натуральное число, большее 2, являющееся одновременно суммой двух квадратов натуральных чисел и суммой двух кубов натуральных чисел. (Ответ: 65=8²+1²=4³+1³)
72. Найти наименьшее натуральное число, большее 1, для которого сумма квадратов последовательных натуральных чисел от 1 до n была бы квадратом натурального числа.
73. Найти наименьшее натуральное n, для которого n⁴ + (n+1)⁴ есть составное число.
74. Найти все числа вида 2ⁿ-1 (где n - натуральное число), не большие миллиона и являющиеся произведениями двух простых чисел.
75. Найдите пять наименьших натуральных чисел n, для которых число n²+1 является произведением трех различных простых чисел, и найдите такое натуральное n, для которого число n²+1 является произведением трех различных простых чисел.
76. Найти пять наименьших натуральных чисел n, для которых число n²-1 является произведением трех различных простых чисел.
77. Найти пять простых чисел, являющихся суммами двухбиквадратов (четвертых степеней) натуральных чисел.
78. Найти наименьшее натуральное число n, такое, что n делится на 2ⁿ-2, но не делится на 3ⁿ-3.
79. Найти наименьшее натуральное число n, такое, что n не делится на 2ⁿ-2, но n делится на 3ⁿ-3.
80. Найти два наименьших составных числа n, таких, что n делится на 2ⁿ-2 и n делится на 3ⁿ-3.
81. Найти пять наименьших натуральных чисел n, для которых каждое из чисел n, n+1, n+2 является произведением двух различных простых чисел. (Ответ: 33=3*11, 34=2*17, 35=5*7; 85=5*17, 86=2*43, 87= 3*29; 93=3*31, 94=2*47, 95= 5*19; 141=3*47, 142=2*71, 143=11*13; 201=3*67, 202=2*101, 203= 7*29; 213=3*71, 214=2*107, 215= 5*43; 217=7*31, 218=2*109, 219= 3*76; 301=7*43, 302=2*151, 303= 3*101)

        Задачи 82-90 заимствованы из Клименченко Д.В. Задачи по математике для любознательных: Кн.для уч-ся 5-6 кл. сред.шк. - М.: Просвещение, 1992. - 192 с.

       

82. Сколько среди двузначных чисел таких, в записи которых: а) имеется хотя бы одна цифра 3; б) число десятков меньше числа единиц? (Ответ: а) 18; б) 36)
83. Сколько среди натуральных чисел, не превосходящих 1000, таких, у которых каждая последующая цифра больше предыдущей? (Ответ: 120)
84. Найти четырехзначное число, две средние цифры которого образуют число, в 5 раз большее числа тысяч и в 3 раза большее числа единиц. (Ответ: 3155)
85. Сколько всего можно записать трехзначных чисел, не используя цифру 7? (Ответ: 648)
86. Расстояние между двумя городами в километрах выражается таким двузначным числом, что левая его цифра равна разности между этим числом и числом, записанным теми же цифрами, но в обратном порядке. Чему равно это расстояние? (Ответ: 98 км)
87. Все натуральные числа от 1 до 100 включительно разбиты на 2 группы - четные и нечетные. Определить, в какой из этих групп сумма всех цифр, использованных для написания чисел, больше и на сколько. (Ответ: Сумма всех цифр нечетных чисел больше суммы всех цифр четных чисел на 49)
88. Количество учеников, обучающихся в V-VI классах школы выражается трехзначным числом. Из цифр этого числа (без повторений их) можно составить 6 различных двузначных чисел, сумма которых вдвое больше числа учеников V-VI классов. Сколько учеников в этих классах? (Ответ: 198 учеников)
89. Найти наименьшее из натуральных чисел, при умножении которого на 2 получается точный квадрат, а при умножении на 3 - точный куб. (Ответ: 72)
90. Найти сумму трехзначных чисел, каждое из которых является произведением четырех неравных между собой простых чисел. (Ответ: 10494)
91. Автоморфными называются числа, которые содержатся в последних разрядах их квадрата. Например: 5²=25, 25²=625. Составьте программу для нахождения нескольких автоморфных чисел.
92. Найти НОД(u_m,u_n), где u_m и u_n - числа Фибоначчи, используя формулу НОД(u_m,u_n) = u_НОД(m,n).
93. Пусть число Фибоначчи u_n делится на некоторое простое число p, причем ни одно из чисел Фибоначчи, меньших u_n, не делится на p. В этом случае мы будем называть число p собственным делителем u_n. Показать, что числа Фибоначчи 1, 8 и 144 собственных делителей не имеют.
94. Найти число Фибоначчи, обладающее несколькими собственными делителями (например, для u₁₉ такими делителями будут числа 37 и 113, для u₂₇ - числа 53 и 109 и т.д.). Много ли чисел Фибоначчи с двумя и более собственными делителями - совершенно не ясно!
95. Вычислить номер члена последовательности Фибоначчи с наперед заданным собственным делителем. (Никакой формулы, позволяющей непосредственно вычислять номера членов с наперед заданным собственным делителем p, пока не известно!)
96. Дана последовательность чисел Фибоначчи, определяемая соотношениями U₁=1, U₂=1, U_n=U_n-1+U_n-2, n>2. Проверить, будет ли U_5k делиться на 5, k=1,2,...
97. Для заданного целого числа m найти среди первых m²-1 чисел Фибоначчи хотя бы одно, делящееся на m.
98. Найти несколько простых чисел Фибоначчи (пока еще не известно конечно или бесконечно число всех простых чисел Фибоначчи).
99. Определите номер числа Фибоначчи, собственным делителем которого является заданное простое p. Учтите, что никакой формулы, позволяющей непосредственно вычислять номера членов с наперед заданным собственным делителем p, пока не известно.

        Последующие задачи составлены по монографии [2] с использованием следующей терминологии.

        Число, записанное как повторение какой-нибудь цифры, называется репдиджитом. Число, записанное одной или более единицами, называется репьюнитом. Будем обозначать R_n - репьюнит, содержащий в своей записи n единиц.

        Длина периода числа n - это количество цифр в периоде десятичного представления дроби 1/n.

        Д.Р.Капрекар назвал число, кратное своей сумме цифр, равной d, Харшад-числом 0 (H-числом ) для d. Например, 247 является H-числом для 13.

        Говорят, что N есть ненулевое H-число для d, если N есть H-число для d и если никакая цифра числа N не равна нулю.

        Пусть S(n) - сумма цифр числа n, а Sp(n) - сумма цифр всех множителей в разложении числа на простые множители.

        Если n составное и S(n)=Sp(n), то n называется числом Смита или просто "смитом". Проверим, например, что число 22 является числом Смита: 22=2*11, S(22)=4, Sp(22)=4.

       

100. Проверьте, что длина периода простого числа, не равного трем, равна числу единиц в наименьшем репьюните, делящемся на это простое число.
101. Проверьте, что любой репьюнит, делящийся на репьюнит R_m, имеет вид R_mn.
102. Проверьте, что длина периода произведения двух простых чисел есть наименьшее общее кратное их длин периодов.
103. Определите длину периода заданного составного числа.
104. Индийский ученый Е.В.Кришнамурти обнаружил, что среди 1226 простых чисел, больших 5 и меньших 10000, отношение числа простых с четной длиной периода к числу простых с нечетной длиной периода равно 2.01 к 1. Проверьте этот факт.
105. Число Капрекара (1981 г.) - это целое n-значное число, квадрат которого равен числу, для которого сумма числа из его крайних справа n цифр и числа из оставшихся крайних слева цифр равна k. Например, 142857²=20408122449. Сумма 20408+122449=142857 является, очевидно, числом Капрекара. Найти еще какое-нибудь число Капрекара.
106. Говорят, что число M имеет Майди-свойство, если длина периода M - четное число и если сумма двух половин периода несократимой дроби со знаменателем M есть репдиджит, состоящий из девяток.
     Показать, что каждое простое с четной длиной периода имеет Майди-свойство, однако составные числа с четной длиной периода не всегда им обладают. Например, 1/21=0(047619). Равенство 047+619=666 показывает, что число 21 не имеет Майди-свойства.
107. Вычислить несколько простых репьюнитов.
108. Может ли репьюнит быть степенью некоторого натурального числа?
109. Существуют ли репьюниты, делящиеся на репьюниты?
110. Найти пару репьюнитов, произведение которых равно 100-значному палиндрому.
111. Чему равен наименьший репьюнит, делящийся на квадрат числа 11?
112. Произведением каких двух репьюнитов является число 123455554321?
113. Найти первые 10 чисел Смита.
114. Обозначим L(p) длину периода простого числа. Найти такое простое число p, что L(p)=L(p³).
115. Проверить утверждение о том, что если p - простое число, отличное от 3, то R_p делит только те простые числа, длина периода которых равна p.
116. Задача Капрекара. Отыскать наименьшее H-число и наибольшее ненулевое H-число для данного d.
117. Проверить, что если m=3^j, то R_m - наибольшее ненулевое H-число для m.
118. Профессоры С.Олтикар и К.Уэйленд из пуэрториканского университета показали, если n>2 и репьюнит R_n простой, то 3304*R_n - "смит". Проверьте этот факт на каком-либо примере.

    На следующем шаге мы приведем задачи, расширяющие возможности учебного интерпретатора языка LISP.

Предыдущий шаг Содержание Следующий шаг