Как понять цифры хэмминга на пальцах?

Question

[TheSnegok]

Не могу понять это, опишите алгоритм на js пожалуйста или обьясните?
Число Хэмминга - это натуральное число вида 2i3j5k для некоторых неотрицательных целых чисел i, j и k.

Comments

[Wataru]

Ну вот 2, 3, 4, 5, 6, 8, 9, 12, 15 - это числа хемминга, потому что они являются произведением сколько-то двоек, троек и пятерок. 7, 14 и 23 - не являются, потому что в разложении на простые множители содержат еще что-то кроме 2, 3 и 5.

Что за алгоритм вам надо описать-то?

[TheSnegok]

Wataru, То-есть числа Хэмминга это числа которые делятся на 2, 3, 5?
а почему 2 является числом хэмминга?

Хочется решить задачу на codewar)

[Wataru]

TheSnegok, Это числа, которые могут делиться только на 2,3 и 5.

2 = 2^1*3^0*5^0

i=1 j=0 k=0

[TheSnegok]

Wataru, Спасибо)

Answer 1

[Rsa97]

Не 2i3j5k, а 2ⁱ×3^j×5^k
Это означает, что при разложении числа на простые множители мы получим только 2, 3 и 5.
1 = 2⁰×3⁰×5⁰
3 = 2⁰×3¹×5⁰
15 = 2⁰×3¹×5¹
30 = 2¹×3¹×5¹
60 = 2²×3¹×5¹
90 = 2¹×3²×5¹
и т.д.

Comments

[TheSnegok]

2, 3 и 5 являются числами хэмминга, ведь они делятся только раз?

[Rsa97]

TheSnegok, Пардон, действительно, я ошибся. Не обязательно должен присутствовать хотя бы один множитель. Сейчас поправлю ответ.

[TheSnegok]

Rsa97, Ничего страшного, всё понятно, огромное спасибо)

Answer 2

[Wataru]

Генерируются они так:

Есть у вас список уже сгенеренных чисел, изначально содержит только 1.

Вы добавляете в список сделющее число, пока не наберете необходимое количество.

Поддерживайте 3 указателя (изначально на первое число), которые указывают на первые неиспользованные числа для домножения на 2, 3 и 5.

Каждый раз берете и сморите что лучше - взять число из первого указателя, домножить на 2, взять число из второго домноженное на 3 или из последнего указателя и домножить на 5. Кладете это число в список и сдвигаете указатель.

Пример:
шаг 1.
указатели: 1, 1, 1
список: {1}
варианты:1*2, 1*3, 1*5. Лучший - 2.

шаг 2.
указатели: 2, 1, 1
список: {1, 2}
варианты:2*2, 1*3, 1*5. Лучший - 3.

шаг 3.
указатели: 2, 2, 1
список: {1, 2, 3}
варианты:2*2, 2*3, 1*5. Лучший - 4.

шаг 4.
указатели: 3, 2, 1
список: {1, 2, 3, 4}
варианты: 3*2, 2*3, 1*5. Лучший - 5.

Comments

[Alexandroppolus]

Мысли вслух. Интересный вопрос: если мы, к примеру, хотим не весь список, а только N-е число, то какой длины список нам реально понадобится к этому алгоритму? Т.е. можно конечно забить и использовать массив N, а можно - кольцевой буфер длиной меньше N. Иными словами, где там будет болтаться указатель для 5. Он будет смотреть на значение, которое равно примерно 1/5 от искомого числа, но поскольку расстояния между соседними числами возрастают, то очевидно что между указателем и последним числом окажется куда менее чем 4N/5 всех чисел..

[Wataru]

Alexandroppolus, Это не так важно, потому что эти самые числа растут експоненциально (если до N их O((lnN)^3) - значит K-ое число порядка O(e^(k^(1/3))). Поэтому гораздо раньше придется беспокоится об длинной арифметике и размере самих чисел, преже чем о их количестве.

Теперь про размер списка. Ваш анализ не совсем точен. N - это само послледнее число. ln N - его длина. Растет оно примерно как количество чисел ^1/3. Таким образом, если вы генерируете первые K чисел, вам надо O(k^2/3) чисел. Не слишком большая экономия.

[Alexandroppolus]

Wataru, да, вы правы (тот коммент удалил, я что-то перепутал количество чисел не более N и первые N чисел, затупил в общем). Если k-ое число порядка O(e^(k^(1/3))), то подставив его в упоминавшийся там квадрат логарифма, как раз и получим O(k^(2/3))...
И действительно, из-за длинной арифметики, эти O(k^(2/3)) самых больших чисел сожрут львиную долю байтов, сведя на нет всю оптимизацию

[Wataru]

Alexandroppolus, Вообще, есть идея не хранить сами числа, а хранить только степени 2, 3 и 5 и вычислять большое число только в самом конце. Но тогда надо уметь 100% точно сравнивать 2 числа в таком виде. Если сравнивать ln2*i+ln3*j+ln5*k, то у дабла должно вполне хватить точности на много дольше, чем если бы в int64_t числа считать.

[mar1kh]

Wataru, Ваш алгоритм только для степеней 2,3,5... Как по Вашему алгоритму должно быть представлено число 6 например? или любое другое, которое получается из перемножения 2,3,5 в степенях?.. а никак потому что алгоритм неправильный.. следующим будет 8

[Wataru]

mar1kh, глупость сказали. Число 6 уже в примере есть в виде кандидата 2*3 и 3*2. Оно как раз следующее и возьмется, потому что 1*5 заменится на 2*5, что будет больше.

[mar1kh]

Wataru, отлично, и какой из двух вариантов сдвинет указатель 2*3 или 3*2?)) я сначала подумал что Вы неправильно написали степень, а Вы вообще имели ввиду умножение)) в таком случае Ваши числа сойдутся только до 12, если даже исключать дубликаты, следующим по порядку будет 14, что не является регулярным числом

[Wataru]

mar1kh,

и какой из двух вариантов сдвинет указатель 2*3 или 3*2?

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

Ваши числа сойдутся только до 12 следующим по порядку будет 14, что не является регулярным числом

И откуда там вообще может взятся 14? Ведь мы каждый раз умножаем число из списка на 2,3 или 5 (указатели в списке, а не топо счетчике же). Дальше по индукции доказывается, что все числа будут регулярными.

Ну вот еще несколько шагов в примере:

указатели: 3, 2, 1
список: {1, 2, 3, 4}
варианты: 3*2, 2*3, 1*5. Лучший - 5.

указатели: 3, 2, 2
список: {1, 2, 3, 4, 5}
варианты: 3*2, 2*3, 2*5. Лучший - 3*2=6.

указатели: 4, 2, 2
список: {1, 2, 3, 4, 5, 6}
варианты: 4*2, 2*3, 2*5. Лучший - 2*3 = 6, но его надо проигнорировать.

указатели: 4, 3, 2
список: {1, 2, 3, 4, 5, 6}
варианты: 4*2, 3*3, 2*5. Лучший - 8

указатели: 5, 3, 2
список: {1, 2, 3, 4, 5, 6, 8}
варианты: 5*2, 3*3, 2*5. Лучший - 9

указатели: 5, 4, 2
список: {1, 2, 3, 4, 5, 6, 8, 9}
варианты: 5*2, 4*3, 2*5. Лучший - 5*2

указатели: 6, 4, 2
список: {1, 2, 3, 4, 5, 6, 8, 9, 10}
варианты: 6*2, 4*3, 2*5. Лучший - 2*5, игнорируем и второй раз 10 не добавляем.

указатели: 6, 4, 3
список: {1, 2, 3, 4, 5, 6, 8, 9, 10}
варианты: 6*2, 4*3, 3*5. Лучший - 6*2

указатели: 8, 5, 3 // обратите внимание - указатель для 2 перешел с числа 6 на число 8.
список: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12}
варианты: 8*2, 5*3, 3*5. Лучший - 5*3, Потом лучшим будет 3*5 и проигнорируется

указатели: 8, 6, 4
список: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15}
варианты: 8*2, 6*3, 4*5. Лучший - 8*2

и т.д.

[TheSnegok]

Wataru, а что значит лучший?

[Wataru]

TheSnegok, Значит минимальный.

[TheSnegok]

Wataru, понял спасибо