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

Целое число, делящееся на сумму своих цифр

В математике число харшад (или число Нивена ) в данной системе счисления — это целое число , которое делится на сумму своих цифр , записанных в этой системе счисления. Числа харшад в системе счисления $n$ также известны как числа $n$ -харшад (или $n$ -нивен ). Числа харшад были определены DR Kaprekar , математиком из Индии . ^[1] Слово «харшад» происходит от санскритского harṣa (радость) + da (давать), что означает даритель радости. Термин «число Нивена» возник из статьи, представленной Иваном М. Нивеном на конференции по теории чисел в 1977 году.

Определение

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

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

$X$ является числом харшад в системе счисления с основанием $n,$ если:

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

Число, которое является числом харшад в любой системе счисления, называется числом all-harshad или числом all-Niven . Существует всего четыре числа all-harshad: 1 , 2 , 4 и 6. Число 12 является числом харшад во всех системах счисления, кроме восьмеричной .

Примеры

Число 18 является числом харшад в десятичной системе счисления , поскольку сумма цифр 1 и 8 равна 9, а 18 делится на 9.
Число Харди–Рамануджана (1729) является числом харшад в десятичной системе счисления, поскольку оно делится на 19, сумму своих цифр (1729 = 19 × 91).
Число 19 не является числом харшад в десятичной системе счисления, поскольку сумма цифр 1 и 9 равна 10, а 19 не делится на 10.
В десятичной системе счисления каждое натуральное число, выраженное в виде 9R _n a _n , где число R _n состоит из n копий одной цифры 1, n > 0, а a _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. ^[2]
Числа харшад в десятичной системе счисления образуют последовательность :
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 12 , 18 , 20 , 21 , 24 , 27 , 30 , 36 , 40 , 42 , 45 , 48 , 50 , 54 , 60 , 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 не является харшадом в десятичной системе счисления, потому что сумма его цифр «11» равна 1 + 1 = 2, а 11 не делится на 2; в то время как в двенадцатеричной системе счисления число 11 может быть представлено как «B», сумма цифр которого также равна B. Поскольку B делится само на себя, оно является харшадом в двенадцатеричной системе счисления.

Хотя последовательность факториалов начинается с чисел харшад в десятичной системе счисления, не все факториалы являются числами харшад. 432! — первое, которое таковым не является. (432! имеет сумму цифр 3897 = 3 ² × 433 в десятичной системе счисления, поэтому не делит 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 ).

Другие базы

Числа харшада в двенадцатеричной системе счисления следующие:

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$

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$ , не являющееся числом харшад по основанию 12, равно (записано в десятичной системе счисления): $k\cdot n$

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 последовательных целых чисел не являются числами харшад в десятичной системе счисления. ^[3]^[4] Они также построили бесконечное множество 20-кортежей последовательных целых чисел, которые все являются числами харшад в десятичной системе счисления, наименьшее из которых превышает ^{1044363342786} .

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

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

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

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

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

Первые запуски точно $н$ последовательные 10-харшад числа

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

$н$	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 ²⁰ − 10	420 142 032 871 116 091 607 294 × 10 ⁴⁰ − 4	неизвестный
$н$	16	17	18	19	20
$х$	50 757 686 696 033 684 694 106 416 498 959 861 492 × 10 ²⁸⁰ − 9	14 107 593 985 876 801 556 467 795 907 102 490 773 681 × 10 ²⁸⁰ − 10	неизвестный	неизвестный	неизвестный

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

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

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

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

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

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

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

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

Каждое натуральное число, не превышающее один миллиард, является либо числом харшад, либо суммой двух чисел харшад. Условно для технической гипотезы о нулях некоторых дзета-функций Дедекинда , Санна доказал, что существует положительное целое число, такое, что каждое натуральное число является суммой не более чем чисел харшад, то есть множество чисел харшад является аддитивным базисом . ^[9] $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 — это суровое число. 16218 имеет сумму цифр 18 18 заканчивается 16218

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

Наименьшее число с суммой цифр n в десятичной системе счисления и оканчивающееся на n, записанное в десятичной системе счисления, равно: (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) определяет множественное число харшад как число харшад, которое при делении на сумму своих цифр дает другое число харшад. ^[11] Он утверждает, что 6804 — это «MHN-4» на том основании, что

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

(это не MHN-5, так как , но 1 не является «еще одним» числом харшада) $1/1=1$

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

Ссылки

^ DR Kaprekar, Многозначные числа , Scripta Mathematica 21 (1955), 27.
^ Росарио Д'Амико, Метод генерации чисел Харшад, в Журнале математической экономики и финансов, т. 5, № 1, июнь 2019 г., стр. 19-26.
^ Купер, Кертис; Кеннеди, Роберт Э. (1993), «О последовательных числах Нивена» (PDF) , Fibonacci Quarterly , 31 (2): 146–151, ISSN 0015-0517, Zbl 0776.11003
^ abc Шандор, Йожеф; Крстичи, Борислав (2004). Справочник по теории чисел II . Дордрехт: Клювер Академик. п. 382. ИСБН 1-4020-2546-7. Збл 1079.11001.
^ Грундман, Х. Г. (1994), «Последовательности последовательных чисел n-Niven» (PDF) , Fibonacci Quarterly , 32 (2): 174–175, ISSN 0015-0517, Zbl 0796.11002
^ Уилсон, Брэд (1997), «Построение 2n последовательных чисел n-Niven» (PDF) , Fibonacci Quarterly , 35 : 122–128, ISSN 0015-0517
↑ Де Конинк, Жан-Мари; Дуайон, Николя (ноябрь 2003 г.), «О числе чисел Нивена вплоть до x », Fibonacci Quarterly , 41 (5): 431–440.
^ Де Конинк, Жан-Мари; Дойон, Николя; Катаи, И. (2003), «О счетной функции для чисел Нивена», Acta Arithmetica , 106 (3): 265–275, Bibcode : 2003AcAri.106..265D, doi : 10.4064/aa106-3-5 .
^ Санна, Карло (март 2021 г.), «Аддитивные основания и числа Нивена», Бюллетень Австралийского математического общества , 104 (3): 373–380, arXiv : 2101.07593 , doi : 10.1017/S0004972721000186 , S2CID 231639019.
^ Боскаро, Сандро (1996–1997), «Нивенморфные целые числа», Журнал занимательной математики , 28 (3): 201–205.
^ Блум, Э. (2005), «Числа Харшада», Журнал занимательной математики , 34 (2): 128.

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

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

[1] DR Kaprekar, Многозначные числа , Scripta Mathematica 21 (1955), 27.

[2] Росарио Д'Амико, Метод генерации чисел Харшад, в Журнале математической экономики и финансов, т. 5, № 1, июнь 2019 г., стр. 19-26.

[3] Купер, Кертис; Кеннеди, Роберт Э. (1993), «О последовательных числах Нивена» (PDF) , Fibonacci Quarterly , 31 (2): 146–151, ISSN 0015-0517, Zbl 0776.11003

[HBII382-4] Шандор, Йожеф; Крстичи, Борислав (2004). Справочник по теории чисел II . Дордрехт: Клювер Академик. п. 382. ИСБН 1-4020-2546-7. Збл 1079.11001.

[5] Грундман, Х. Г. (1994), «Последовательности последовательных чисел n-Niven» (PDF) , Fibonacci Quarterly , 32 (2): 174–175, ISSN 0015-0517, Zbl 0796.11002

[6] Уилсон, Брэд (1997), «Построение 2n последовательных чисел n-Niven» (PDF) , Fibonacci Quarterly , 35 : 122–128, ISSN 0015-0517

[7] Де Конинк, Жан-Мари; Дуайон, Николя (ноябрь 2003 г.), «О числе чисел Нивена вплоть до x », Fibonacci Quarterly , 41 (5): 431–440.

[8] Де Конинк, Жан-Мари; Дойон, Николя; Катаи, И. (2003), «О счетной функции для чисел Нивена», Acta Arithmetica , 106 (3): 265–275, Bibcode : 2003AcAri.106..265D, doi : 10.4064/aa106-3-5 .

[9] Санна, Карло (март 2021 г.), «Аддитивные основания и числа Нивена», Бюллетень Австралийского математического общества , 104 (3): 373–380, arXiv : 2101.07593 , doi : 10.1017/S0004972721000186 , S2CID 231639019.

[10] Боскаро, Сандро (1996–1997), «Нивенморфные целые числа», Журнал занимательной математики , 28 (3): 201–205.

[11] Блум, Э. (2005), «Числа Харшада», Журнал занимательной математики , 34 (2): 128.