Как определить, что число - произведение степеней двоек минус единица?

Answer 1

надо разложить на простые множители, потом кумекать.
-
-
4 - 1 = 3
8 - 1 = 7
16 - 1 = 15
32 - 1 = 31
.
-
составить такой список до самого числа. провести проверку на простые числа.
простые числа, сответствующие формуле 2^n -1, сокращённо обозначим пч1
-
разложить на простые множители составные числа этого списка. простые числа, получившиеся таким образом и не являющиеся пч1, обозначим пч2.
-
-
1. если число разлагается только на пч1, то можно.
2. если в разложении есть простые числа, которых нет ни среди пч1 ни среди пч2, то нельзя.
-
-
а вот если не случай 1 и не случай 2, то сложне.
-
проверим число на делимость на составные числа нашего списка. если не делится ни на одно из них, то нельзя.
все случаи когда делится, нужно исследовать. т. е. поделить и изучить частное так, как это уже было описано выше….
-
-
рассмотрим работу алгоритма на исходном примере. число 135
4 - 1 = 3 простое
8 - 1 = 7 простое
16 - 1 = 15 = 3*5
32 - 1 = 31 простое
64 – 1 = 63 = 3^2*7
128 – 1 = 127 = простое
-
итак
пч1 – 3; 7; 31; 127
пч2 – 5
-
135 = 3^3*5
т. е. наш третий случай.
135 делится только на 15.
частное 9. частное разлагается только на пч1. вуаля!
-
-
теперь число 100
100 = 5^2*2^2
2 не входит ни в пч1 ни в пч2. вуаля!

Answer 2

Любое число вида x= 2^n-1. То есть n=log2 (x - целое. Проверить целостность. Целая степень двойки в двоичной записи определяется на глаз или подсчётом количества единиц (1 шт, если чо) .