Тамарины числа

[Ktina]

Назовём натуральное число, большее 1, Тамариным, если каждый следующий его делитель больше предыдущего либо на 1, либо вдвое.

Верно ли, что любое Тамарино число является либо степенью двойки (с натуральным показателем), либо степенью двойки (с натуральным показателем), умноженной на следующее за ней число?

[wrest]

Ktina в сообщении #1330862 писал(а):

степенью двойки (с натуральным показателем), умноженной на следующее за ней число?

Кто за кем тут следует?

[gris]

Наверное, имеется в виду число, следующее за именно этой степенью двойки. То есть, например:
$2^1\cdot (2^1+1)=6:1,2,3,6$
$2^2\cdot (2^2+1)=20:1,2,4,5,10,20$
$2^8\cdot (2^8+1)=...$
Я бы даже немного усилил, потребовав, чтобы это следующее число было простым. Тогда бы условие работало в обе стороны (в одну достаточно легко показать).

[wrest]

Если $p=2^n+1$ простое, то $t=2^n\cdot (2^n+1)$ - Тамарино.
И наоборот, "нетривиальное" Тамарино число (не являющееся степенью двойки) $t$ только такое что $t=2^n\cdot(2^n+1)$ где $2^n+1$ -- простое.
Таких чисел науке известно только 5.

-- 06.08.2018, 14:12 --

gris
Да, вы правы. Вторым простым множителем в разложении должно быть простое число Ферма. Коих покашта только 5 штук.

-- 06.08.2018, 14:35 --

Функция, которая "честно" проверяет, является ли число Тамариным и возвращает 1 если да и 0 если нет:

Ktina128915(n)=my(dv=divisors(n),dn=#dv);if(n<2,return(0));for(i=2,dn,if(dv[i-1]*2==dv[i],next,if(dv[i]-dv[i-1]==1,next,return(0))));return(1)

[Ktina]

wrest в сообщении #1330876 писал(а):

Ktina в сообщении #1330862 писал(а):

степенью двойки (с натуральным показателем), умноженной на следующее за ней число?

Кто за кем тут следует?

Вы правы, разумеется
Не за двойкой, а за степенью.
https://www.youtube.com/watch?v=rASm-qr19_o

[kotenok gav]

wrest в сообщении #1330880 писал(а):

простое число Ферма

Мерсенна...

[wrest]

kotenok gav в сообщении #1330884 писал(а):

Мерсенна...

Нет, Мерсенна это другие. Тут числа Ферма: https://ru.wikipedia.org/wiki/%D0%A7%D0 ... 0%BC%D0%B0

[kotenok gav]

Ферма - это когда степень двойки в показателе. А тут не так.

[gris]

Если в показателе не степень двойки, то увеличенная степень алгебраически разложима на множители (для любого допустимого основания). У Мерсенна степень уменьшается на единичку. Впрочем, число $3$ является и таким, и таким

[wrest]

kotenok gav в сообщении #1330896 писал(а):

Ферма - это когда степень двойки в показателе. А тут не так.

Что не так?
$2^n+1$ простые только если $n=2^k$ и то не для всех $k$ а только для пяти, с нуля по четыре. Другие $k$ [пока] науке неизвестны.

[kotenok gav]

wrest в сообщении #1330898 писал(а):

$2^n+1$ простые только если $n=2^k$

А где прочесть док-во?

[mihaild]

Пусть $k = ab$, где $a$ нечетное. Чему равен остаток от деления $2^k + 1$ на $2^b + 1$?

[grizzly]

kotenok gav в сообщении #1330900 писал(а):

А где прочесть док-во?

Тренируйтесь, перед тем как задавать подобные вопросы, посмотреть Википедию. Там не всегда всё есть и не всегда всё правильно, но в 9 случаях из 10 Вам этого будет вполне достаточно.

[kotenok gav]

mihaild в сообщении #1330902 писал(а):

Чему равен остаток от деления $2^k + 1$ на $2^b + 1$?

А, понял.

[JohnDou]

(Ответ)

Верно

(Решение)

Нетрудно заметить что т-числом могут быть только чётные числа. Допустим теперь что существует т-число хотя бы с двумя нечётными делителями. Пусть самым большим из них будет $b$, а тот что перед ним - $a$. Тогда т-число должно делиться на $2a$ и $2b$. Ясно что при переходе от $2a$ к $2b$ мы не можем применять операцию "+1", а значит¹ $2^k\cdot a= 2b$ или $b=2^{k-1}\cdot a$ противоречие! Следовательно, утверждение доказано².



¹:Случай когда $b=2^ka+1$ исключён т.к. тогда самым большим нечетным делителем будет $a\cdot b$

²: если в т-числе степень двойки выше степени двойки участвующей в формировании простого числа, создаётся ситуация $2^k<p<2^{k+1}$ которая сводится к вышеописанному