[seqfan] Re: A005360 complete?

[Maximilian Hasler]

For what it's worth, I have written Jack's algorithm in PARI, see below.
("word by word translation", without any attempt on optimization).
It seems to work correctly:

for(n=1,99, is_flimsy(n) && print1(n","))
11,13,19,22,23,25,26,27,29,37,38,39,41,43,44,46,47,50,52,53,54,55,57,
58,59,61,67,71,74,76,77,78,79,81,82,83,86,87,88,91,92,94,95,97,99,

Maximilian

%o A005360 (PARI)
is_flimsy = is_A005360 = n -> { my(t,S);
bittest(n,0) && n >>= valuation(n,2);
S=Set(t=Mod(1,n)); /* construct set of residues */
while( #S < #S=setunion(S,Set(t*=2)),); S=eval(S);
for( k=2,norml2(binary(n))-1, /* number of terms */
forvec( v=vector( k, i, [1,#S]), sum(j=1,k, S[v[j]]) || return(1)
,1 /*increasing forvec*/))}



On Mon, Jul 14, 2008 at 12:19 PM, Jack Brennen <jb at brennen.net> wrote:
> 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.
>
>