Find the sum of the number of constructible polygons 
Let $R(n)$ equal $1$ if a regular $n$-sided polygon is constructible with a ruler and compass and $0$ if it is not. What is $\displaystyle \sum_{n = 3}^{100}R(n)$?

This question seems very hard to solve without just listing out all $n$ and seeing which $n$ have $\phi(n) = 2^m$. Is there any simple method to solve this question?
 A: 1573035
There is a version of the Pascal Triangle which may be of use to you. It consists of the modulo-2 residues of the members of the Triangle. 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}$    
Notice that
(1) each new row is one item longer than its predecessor and always begins and ends with 1;
(2.1) a 0/0 or 1/1 pair yields a 0 in the next row;
(2.2) a 0/1 or 1/0 pair yields a 1 in the next row.    
Each of these rows may be considered as a digit-by-digit representation of a binary number. Excepting the apex, each of these binary numbers represents the number of sides of a constructible odd-number regular polygon in ascending order of size. The final valid number in the series is $2^{32}-1$, the product $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.
So, your answer is 19.
====================
(written in QB64)
FUNCTION R~`(n~%%)
-->a~%% = n~%% 'make copy of argument    
'eliminate powers of 2 from argument
-->WHILE((a~%% MOD 2) = 0)
----->a~%% = a~%% \ 2
-->WEND    
'eliminate single instances of allowed odd factors from argument
-->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 if constructible, 0 if not
END FUNCTION    
