Номер Харшада

В математике число Харшада (или число Нивена ) в данной системе счисления представляет собой целое число , которое делится на сумму своих цифр при записи в этой системе счисления. Числа Харшада по основанию n также известны как числа n -харшада (или n -нивена ). Числа Харшада были определены Д. Р. Капрекаром , математиком из Индии . Слово «харшад» происходит от санскритского harṣa (радость) + da (давать), что означает «дающий радость». Термин «число Нивена» возник из статьи Ивана М. Нивена на конференции по теории чисел в 1977 году.

Определение

С математической точки зрения, пусть X будет положительным целым числом с m цифрами, записанным по основанию n , и пусть цифры будут $a_{i}$ ( $i=0,1,\ldots ,m-1$). (Из этого следует, что $a_{i}$ должен быть нулем или целым положительным числом до ⁠ $n-1$⁠ .) X можно выразить как

$X=\sum _{i=0}^{m-1}a_{i}n^{i}.$

X — число Харшада по основанию n, если:

$X\equiv 0{\bmod {\sum _{i=0}^{m-1}a_{i}}}.$

Число, которое является числом Харшада в каждой системе счисления, называется числом Харшада или числом Нивена . Есть только четыре жестких числа: 1 , 2 , 4 и 6 . Число 12 — это число Харшад во всех основаниях, кроме восьмеричного .

Примеры

• Число 18 является числом Харшада по основанию 10 , поскольку сумма цифр 1 и 8 равна 9, а 18 делится на 9.
• Число Харди-Рамануджана (1729) представляет собой число Харшада по основанию 10, поскольку оно делится на 19, сумму своих цифр (1729 = 19 × 91).
• Число 19 не является числом Харшада по основанию 10, поскольку сумма цифр 1 и 9 равна 10, а 19 не делится на 10.
• В системе счисления 10 — каждое натуральное число, выражаемое в форме 9R _n a _n , где число R _n состоит из n копий одной цифры 1, n > 0, а n _— целое положительное число меньше 10. ^н и кратное n , является числом Шаршада. (Р. Д'Амико, 2019). Число 9R ₃ a ₃ = 521478, где R ₃ = 111, n = 3 и a ₃ = 3×174 = 522, является числом шаршада; на самом деле имеем: 521478/(5+2+1+4+7+8) = 521478/27 = 19314.
• Числа Харшада по основанию 10 образуют последовательность :

  1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 12 , 18 , 20 , 21 , 24 , 27 , 30 , 36 , 42 , 45 , 48 , 50 , 54 , 60 , , 40 63 , 70 , 72 , 80 , 81 , 84 , 90 , 100 , 102 , 108 , 110 , 111 , 112 , 114 , 117 , 120 , 126 , 132 , 133 , 135 , 140 , 150 , 152 , 153 , , ​ 156 , 162 , 171 , 180 , 190 , 192 , 195 , 198, 200 , ... (последовательность A005349 в OEIS ).

• Все целые числа от нуля до n являются числами n -харшада.

Характеристики

Учитывая критерий делимости 9, может возникнуть соблазн обобщить, что все числа, делящиеся на 9, также являются числами Харшада. Но для определения резкости n цифры n можно сложить только один раз, и n должно делиться на эту сумму; в противном случае это не число Харшада. Например, 99 не является числом Харшада, так как 9+9=18, а 99 не делится на 18.

Базовое число (а тем более, его степени) всегда будет числом харшад в своей собственной базе, поскольку оно будет представлено как «10» и 1 + 0 = 1.

Все числа, чья сумма цифр по основанию b делит b −1, являются числами Харшада по основанию b .

Чтобы простое число также было числом Харшада, оно должно быть меньше или равно базовому числу, в противном случае сумма цифр простого числа составит число, которое больше 1, но меньше простого числа, и не будет делимый. Например: 11 не является харшадом по основанию 10, потому что сумма его цифр «11» равна 1 + 1 = 2, а 11 не делится на 2; в то время как в базе 12 число 11 может быть представлено как «B», сумма цифр которого также равна B. Поскольку B делится само на себя, в системе счисления 12 оно делится на харшад.

Хотя последовательность факториалов начинается с чисел Харшада по основанию 10, не все факториалы являются числами Харшада. 432! это первое, чего нет. (432! имеет сумму цифр 3897 = 3 ² × 433 по основанию 10, поэтому 432 не делится!)

Наименьшее k такое, что $k\cdot n$ это число Харшада

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10, 1, 9, 3, 2, 3, 6, 1, 6, 1, 1, 5, 9, 1, 2, 6, 1, 3, 9, 1, 12, 6, 4, 3, 2, 1, 3, 3, 3, 1, 10, 1, 12, 3, 1, 5, 9, 1, 8, 1, 2, 3, 18, 1, 2, 2, 2, 9, 9, 1, 12, 6, 1, 3, 3, 2, 3, 3, 3, 1, 18, 1, 7, 3, 2, 2, 4, 2, 9, 1, ... (последовательность A144261 в OEIS ).

Наименьшее k такое, что $k\cdot n$ это не число Харшада

11, 7, 5, 4, 3, 11, 2, 2, 11, 13, 1, 8, 1, 1, 1, 1, 1, 161, 1, 8, 5, 1, 1, 4, 1, 1, 7, 1, 1, 13, 1, 1, 1, 1, 1, 83, 1, 1, 1, 4, 1, 4, 1, 1, 11, 1, 1, 2, 1, 5, 1, 1, 1, 537, 1, 1, 1, 1, 1, 83, 1, 1, 3, 1, 1, 1, 1, 1, 1, 5, 1, 68, 1, 1, 1, 1, 1, 1, 1, 2, ... (последовательность A144262 в OEIS ).

Другие базы

Числа харшадов по основанию 12 :

1, 2, 3, 4, 5, 6, 7, 8, 9, А, Б, 10, 1А, 20, 29, 30, 38, 40, 47, 50, 56, 60, 65, 70, 74, 80, 83, 90, 92, А0, А1, Б0, 100, 10А, 110, 115, 119, 120, 122, 128, 130, 134, 137, 146, 150, 153, 155, 164, 172, 173, 182, 191, 1А0, 1В0, 1БА, 200, ...

где A представляет десять, а B представляет одиннадцать.

Наименьшее k такое, что $k\cdot n$ число Харшад по основанию 12 (записано по основанию 10):

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 12, 6, 4, 3, 10, 2, 11, 3, 4, 1, 7, 1, 12, 6, 4, 3, 11, 2, 11, 3, 1, 5, 9, 1, 12, 11, 4, 3, 11, 2, 11, 1, 4, 4, 11, 1, 16, 6, 4, 3, 11, 2, 1, 3, 11, 11, 11, 1, 12, 11, 5, 7, 9, 1, 7, 3, 3, 9, 11, 1, ...

Наименьшее k такое, что $k\cdot n$ не является числом Харшада по основанию 12 (записано по основанию 10):

13, 7, 5, 4, 3, 3, 2, 2, 2, 2, 13, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 157, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 157, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1885, 1, 1, 1, 1, 1, 3, ...

Как и в случае с основанием 10, не все факториалы являются числами Харшада с основанием 12. После 7! (= 5040 = 2B00 по основанию 12, сумма цифр 13 по основанию 12, а 13 не делит 7!), 1276! это следующее, чего нет. (1276! имеет сумму цифр 14201 = 11 × 1291 по основанию 12, поэтому не делит 1276!)

Последовательные числа Харшада

Максимальное количество последовательных номеров харшадов

Купер и Кеннеди доказали в 1993 году, что никакие 21 последовательные целые числа не являются числами Харшада по основанию 10. Они также построили бесконечное множество кортежей из 20 последовательных целых чисел, которые представляют собой 10-значные числа, наименьшее из которых превышает 10. ^44363342786 .

Х.Г.Грундман ( 1994 ) расширил результат Купера и Кеннеди, показав, что существует 2b, но не 2b +1 последовательных b -жестких чисел для любого основания b . , чтобы показать, что существует бесконечно много серий из 2 b последовательных чисел b -харшада для b = 2 или 3. Этот результат был усилен Т. Кай ( 1996 ) и для произвольного b Брэда Уилсона в 1997 году.

Таким образом, в двоичном формате существует бесконечно много серий из четырех последовательных чисел харшад, а в троичной - бесконечно много серий из шести.

В общем случае такие максимальные последовательности выполняются из N · b ^к − b к N · b ^к + ( b − 1), где b — основание, k — относительно большая степень, а N — константа. Учитывая одну такую ​​подходяще выбранную последовательность, мы можем преобразовать ее в более крупную следующим образом:

• Вставка нулей в N не изменит последовательность цифровых сумм (так же, как 21, 201 и 2001 — все 10-значные числа).
• Если мы вставим n нулей после первой цифры, α (стоимостью αb ^я ), увеличиваем значение N на αb ^я ( б ^н − 1).
• Если мы сможем гарантировать, что b ^н − 1 делится на все суммы цифр в последовательности, то делимость на эти суммы сохраняется.
• Если наша исходная последовательность выбрана так, что суммы цифр взаимно просты с b , мы можем решить b ^н = 1 по модулю всех этих сумм.
• Если это не так, но часть каждой суммы цифр, не взаимно простая с b, делит αb ^я , то делимость сохраняется.
• (Недоказано) Таким образом выбрана начальная последовательность.

Таким образом, наша исходная последовательность дает бесконечное множество решений.

Первые прогоны ровно n последовательных 10-значных чисел

Наименьшие натуральные числа, начинающие серии ровно из n последовательных 10-значных чисел (т. е. наименьшее x такое, что $x,x+1,\cdots ,x+n-1$ это числа Харшада, но $x-1$ и $x+n$ не являются) следующие (последовательность A060159 в OEIS ):

н	1	2	3	4	5
х	12	20	110	510	131 052
н	6	7	8	9	10
х	12 751 220	10 000 095	2 162 049 150	124 324 220	1
н	11	12	13	14	15
х	920 067 411 130 599	43 494 229 746 440 272 890	121 003 242 000 074 550 107 423 034 × 10 20  − 10	420 142 032 871 116 091 607 294 × 10 40  − 4	неизвестный
н	16	17	18	19	20
х	50 757 686 696 033 684 694 106 416 498 959 861 492 × 10 280  − 9	14 107 593 985 876 801 556 467 795 907 102 490 773 681 × 10 280  − 10	неизвестный	неизвестный	неизвестный

Согласно предыдущему разделу такого x не существует для $n>20.$

Оценка плотности чисел харшадов

Если мы позволим $N(x)$ обозначают количество чисел харшадов $\leq x$, то для любого данного $\varepsilon >0,$

$x^{1-\varepsilon }\ll N(x)\ll {\frac {x\log \log x}{\log x}}$

как показали Жан-Мари Де Конинк и Николя Дойон; кроме того, Де Конинк, Дойон и Катаи доказал, что

$N(x)=(c+o(1)){\frac {x}{\log x}},$

где $c=(14/27)\log 10\approx 1.1939$ и $o(1)$ термин использует обозначение Big O.

Суммы чисел Харшада

Каждое натуральное число, не превышающее одного миллиарда, является либо числом харшада, либо суммой двух чисел харшада. При условии технической гипотезы о нулях некоторых дзета-функций Дедекинда Санна доказал, что существует целое положительное число. $k$ такая, что каждое натуральное число является суммой не более $k$ числа харшадов, то есть набор чисел харшадов представляет собой аддитивную основу .

Количество способов, которыми каждое натуральное число 1, 2, 3, ... можно записать в виде суммы двух чисел Харшад, равно:

0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 3, 4, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 3, 2, 4, 3, 3, 4, 3, 3, 5, 3, 4, 5, 4, 4, 7, 4, 5, 6, 5, 3, 7, 4, 4, 6, 4, 2, 7, 3, 4, 5, 4, 3, 7, 3, 4, 5, 4, 3, 8, 3, 4, 6, 3, 3, 6, 2, 5, 6, 5, 3, 8, 4, 4, 6, ... (последовательность A337853 в OEIS ).

Наименьшее число, которое можно записать ровно 1, 2, 3, ... способами, как сумму двух чисел харшада:

2, 4, 6, 8, 10, 51, 48, 72, 108, 126, 90, 138, 144, 120, 198, 162, 210, 216, 315, 240, 234, 306, 252, 372, 270, 546,360,342,444,414,468,420,642,450,522,540,924,612,600,666,630,888,930,756,840,882,936,972,1098,1 215, 1026, 1212, 1080, ... (последовательность A337854 в OEIS ).

Нивенморфные числа

или Нивенморфное число харшадморфное число для данной системы счисления — это целое число t такое, что существует некоторое харшадное число N, которого сумма цифр равна t , и t , записанное в этой базе, завершает N, записанное в той же базе.

Например, 18 — это нивенморфное число по основанию 10:

 16218 is a harshad number
 16218 has 18 as digit sum
    18 terminates 16218

Сандро Боскаро определил, что по основанию 10 все положительные целые числа являются нивенморфными числами, кроме 11 . Фактически, для четного целого числа n > 1 все положительные целые числа, кроме n +1, являются нивенморфными числами по основанию n , а для нечетного целого числа n > 1 все положительные целые числа являются нивенморфными числами по основанию n . например, нивенморфные числа в базе 12 — это OEIS : A011760 (все положительные целые числа, кроме 13).

Наименьшее число с суммой цифр по основанию 10 n и оканчивающееся n, записанное по основанию 10: (0, если такого числа не существует)

1, 2, 3, 4, 5, 6, 7, 8, 9, 910, 0, 912, 11713, 6314, 915, 3616, 15317, 918, 17119, 9920, 18921, 9922, 82823, 19824, 9925, 46826, 18927, 18928, 78329, 99930, 585931, 388832, 1098933, 198934, 289835, 99936, 99937, 478838, 198939, 1999840, 2988941 , 2979942, 2979943, 999944, 999945, 4698946, 4779947, 2998848, 2998849, 9999950, ... (последовательность A187924 в OEIS )

Несколько номеров Харшада

Блум (2005) определяет множественное число харшада как число харшада, которое при делении на сумму своих цифр дает другое число харшада. Он заявляет, что номер 6804 — это «MHN-4» на том основании, что

${\begin{aligned}6804/18&=378\\378/18&=21\\21/3&=7\\7/7&=1\end{aligned}}$

(это не МХН-5 т.к. $1/1=1$, но 1 - это не "еще один" номер харшада)

и далее показал, что 2016502858579884466176 — это MHN-12. Число 10080000000000 = 1008×10 ¹⁰ , который поменьше, тоже МХН-12. В общем 1008×10 ^н есть MHN-( n +2).

Внешние ссылки

Вайсштейн, Эрик В. «Число Харшада» . Математический мир .