Hallar la suma del número de polígonos construibles

Question

Dejemos que $R(n)$ igual $1$ si se trata de un $n$ -es construible con regla y compás y $0$ si no lo es. ¿Qué es? $\displaystyle \sum_{n = 3}^{100}R(n)$ ?

Esta pregunta parece muy difícil de resolver sin enumerar todos los $n$ y ver qué $n$ tienen $\phi(n) = 2^m$ . ¿Hay algún método sencillo para resolver esta cuestión?

Answer 1

1573035
Existe una versión del Triángulo de Pascal que puede serle útil. Consiste en los residuos del módulo 2 de los miembros del Triángulo. Observe:

$\begin{array}{ccccccccccccccc|l} &&&&&&&1&&&&&&&&=1\\ &&&&&&1&&1&&&&&&&=3\\ &&&&&1&&0&&1&&&&&&=5\\ &&&&1&&1&&1&&1&&&&&=15\\ &&&1&&0&&0&&0&&1&&&&=17\\ &&1&&1&&0&&0&&1&&1&&&=51\\ &1&&0&&1&&0&&1&&0&&1&&=85\\ 1&&1&&1&&1&&1&&1&&1&&1&=255 \end{array}$

Observe que
(1) cada nueva fila es un elemento más largo que su predecesor y siempre comienza y termina con 1;
(2.1) un par 0/0 o 1/1 produce un 0 en la siguiente fila;
(2.2) un par 0/1 o 1/0 produce un 1 en la siguiente fila.

Cada una de estas filas puede considerarse como una representación dígito a dígito de un número binario. Exceptuando el vértice, cada uno de estos números binarios representa el número de lados de un polígono regular construible con números Impares en orden ascendente de tamaño. El último número válido de la serie es $2^{32}-1$ el producto $3\times 5\times 17\times 257\times 65537$ .

3,5,6,10,12,15,17,20,24,30,34,40,48,51,60,68,80,85,96.
Por lo tanto, su respuesta es 19.

\==================== (escrito en QB64)
FUNCIÓN R~`(n~%%)
-->a~%% = n~%% 'hacer copia del argumento

'eliminar las potencias de 2 del argumento
-->WHILE((a~%% MOD 2) = 0)
----->a~%% = a~%% \ 2
-->WEND

'eliminar las instancias individuales de los factores Impares permitidos del argumento
-->IF((a~%% MOD 3) = 0) THEN a~%% = a~%% \ 3
-->IF((a~%% MOD 5) = 0) THEN a~%% = a~%% \ 5
-->IF((a~%% MOD 17) = 0) THEN a~%% = a~%% \ 17
-->IF((a~%% MOD 257) = 0) THEN a~%% = a~%% \ 257
-->IF((a~%% MOD 65537) = 0) THEN a~%% = a~%% \ 65537

-->R~` = (a~%% = 1) 'R = 1 si es construible, 0 si no
FIN DE LA FUNCIÓN