Занимательная математика

[spamsink]

До меня дошли слухи, что существует хотя бы одно число 0 < x < 1, представление которого в двоичной и в троичной системе в точности совпадает, начиная с некоторого знака.

Понятно, что это должно быть какое-то иррациональное число, но как его получить хотя бы приблизительно численными методами, я не представляю себе.

Математики, ау!

Comments

[ircicq]

1/2:

в двоичной одно из представлений: 0.01111111111...

в троичной: 0.111111111...

[spamsink]

Я думаю, этот тривиальный случай, возможно, не считается. Автор задачи заявляет, что нашел уже пять таких чисел.

[spamsink]

Я нашёл несколько рациональных чисел, удовлетворяющих задаче без чита с 11111... в двоичной системе.

[zyxman]

Так а разве так сложно в лоб перебрать весь диапазон фп32? (single precision float)

[spamsink]

Так они ж там все рациональные, со знаменателями, равными степени двойки.

[spamsink]

На самом деле для рациональных чисел это решается перебором степеней двойки и тройки и рассмотрением чисел, на 1 меньших, чем эти степени, для выяснения, какой длины должен быть период (а зная период, понятно, какой должен быть знаменатель, и перебрать числители тривиально).

3^2 = 2^3+1 даёт одну пару решений (1/24 и 11/24),
сочетание 3^4 = 2^4*5+1, 2^4 = 3*5+1 даёт знаменатель 240 и другую пару решений: после сокращения, 3/20 и 7/20.

Пятым (формальным) решением считается 1/2.

[ircicq]

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

Интересно, можно ли решить не перебором а на бумажке.

[spamsink]

На бумажке можно. Я, собственно, так наполовину и решил. Число x/y должно быть равно а/2^n + b/(2^m-1) и c/3^n + d/(3^m-1). Для того, чтобы обе суммы смогли в конце концов сократиться до общего знаменателя, у числа 3^m-1 и 2^m-1 все делители, за исключением степеней чисел 2 и 3, должны быть общими. Для m=2 это верно, поскольку 2^2-1 = 3 и 3^2-1 = 8 этой проблемы не имеют вовсе. Оттого достаточно рассмотреть дроби со знаменателем 3*8=24.

Для m=3 у чисел 7 и 26 нет ничего общего. Для m=4 числа 80 и 15 годятся, у них общий делитель 5. Их общее кратное 240.

Для других значений m, насколько можно видеть, общих делителей не будет. Дальше для каждого m можно написать диофантово уравнение и пытаться его решать на бумажке, но проще перебором. Тем более что перебирать нужно только дроби меньше 1/2 (иначе в троичной записи двойки появляются).

[zyxman]

ну будет чуть медленней если нельзя стандартные оптимизированные либы использовать.

А что степени, так это же ускорение, меньше перебирать прийдется.