A005360 complete?

Jack Brennen jb at brennen.net
Mon Jul 14 18:19:38 CEST 2008


To determine if an odd number N is flimsy, take the finite set of residues of 2^a (mod N).
Assume that the number of 1's in the binary representation of N is equal to C.

To show that the number is flimsy, find a way to construct zero by adding up some number
of residues of 2^a (mod N) using less than C terms.  To show that the number is sturdy,
show that it's impossible to do so.

For instance, for the number 37, which has 3 ones in its binary representation, the
set of residues of 2^a (mod 37) is actually all of the numbers except zero.  Clearly
we can find two that sum to zero.  :)  So 37 is flimsy.

On the other hand, for the number 15, which has 4 ones in its binary representation,
the set of residues of 2^a (mod 15) is:  1, 2, 4, 8.  It is impossible to sum 2 or 3
of these to add up to zero.






More information about the SeqFan mailing list