[seqfan] Re: A005360 complete?
Maximilian Hasler
maximilian.hasler at gmail.com
Sun Dec 20 22:47:59 CET 2009
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.
>
>
More information about the SeqFan
mailing list