Conference rusure::math

    >What is the asymptotic growth of s ?
    >                                  n

    first, is this an infinite sequence? by intuition i think so.

    by intuition, i'd say the gaps become very large between s(n) and s(n+1)
    as n->oo , i'd guess s(n+1)-s(n) = O(n^3) for larg n, or something as
    such but this is just a guess.
    
    i dont know you'd do this analytically without writing a program
    and looking for the pattern, but i have a feeling there is a way to do it
    analytically .

    >Find another increasing sequence t , t , t , ... that shares this
    >                                  1   2   3
    >square-free property, but which has a smaller growth rate.
     
    I dont understand this one, if both sequences start with 2,3,5,10,27,.. then
    both sequences will be identical, unless you skip over some numbers
    in one sequence, and include these skipped numbers in the other?

    i mean, the next larger to be added to the sequence, will depend on what
    numbers already in the sequence (to keep it square free), so there is
    only one such sequence.

    do you mean the sequences not necessarily both start from 2? and/or need
    not contain same numbers ...

    ok, i better shut up and go and make coffee, iam not doing well on
    this one..
    
    /nasser

    there is in MAPLE a procedure called SUBSETS in the COMBINATE package
    this proc iterate over the power set of a set .

    you call it once, it generate the power set, then you iterate over
    each set in the power set until a flag is set by MAPLE telling you
    no more sets.

    so this could be used to build up the square free sequence.

    i.e. add a number to the sequence, make sure it is still square free
    or not by testing all the sets in the power set that they dont add to
    a square, if you found one adds to square, throw away the number and
    try the next.

    something like this.. 
    
    >with(combinate):
    >power_set := subsets({2,3,5,10,27,28}):
    >while not power_set[finished] do 
    >   list:= power_set[nextvalue] () 
    >   sum:= sum_of_list(list);
    >   if is_square(sum) exit;
    >   od;
    >... if you get here => number 28 can be added to main sequence
    >... now try  
    etc..
    
    

        If you already have t1, t2, ..., tn with nonsquare sums,
        then you can append t(n+1) if each of the 2^n sums t(n+1)
        + sum(S) for S a subset of {t1,...,tn} is not a square. 
        These numbers range from t(n+1) to t(n+1) + (t1+...+tn). 
        All of those can be made non-square, for example, by
        having them fall strictly between two consecutive
        squares, e.g., having t(n+1) = x^2 + 1 where x^2 + 2x + 1
        exceeds t(n+1) + (t1+...+tn), i.e., x > (t1+...+tn)/2. So
        any such sequence can be extended indefinitely.  (Of
        course, a smaller t(n+1) may work as well.)
        
        Dan

>    The integer sequence s , s , s , ... is defined so that s  is
>                          1   2   3                          n
>    the smallest positive integer such that every non-empty subset of
	 ^^^^^^^^
>    
>    { s , s , ..., s  } sums to a non-square.
>       1   2        n
    
Doesn't the definition make the sequence unique?

        The s1, s2, ... sequence is unique, because at each point
        the smallest appropriate positive integer must be chosen.
        But without that restriction other sequences t1, t2, ...
        exist with non-square sums.
        
        Dan

re .1

>>Find another increasing sequence t1, t2 , t3, ... that shares this
>>square-free property, but which has a smaller growth rate.
>I dont understand this one, if both sequences start with 2,3,5,10,27,.. then
>both sequences will be identical, unless you skip over some numbers
>in one sequence, and include these skipped numbers in the other?

The t sequence needn't take t_n to be the *smallest* integer that preserves
the square-free property.  This gives a different sequence, and may give a
smaller growth rate!

>do you mean the sequences not necessarily both start from 2? and/or need
>not contain same numbers ...

Right.

re .3:

That's one way to form such a sequence.  Start with 2,3,5.  Then you can take

	t_n = [ (t1+t2+...+t<n-1> )/2 ]^2 - 1,

where [x] is the floor function.  So t_n is nonsquare, and t_n + 2 thru
t_n + (t1+t2+...+t<n-1>) are nonsquare, because t_n + (t1+t2+...+t<n-1>) is less
than [(t1+t2+...+t<n-1>)/2 + 1]^2, which is the next square greater than t_n+1.
The sequence proceeds: 2,3,5,24,288,25920,172160640,7412080583220480, ....
After the first few terms, the next term after P is P*(P/4 + sqrt(P+1) + 1),
so t_n grows faster than 4 * 1.147^(2^n).

    Surely a better (the best?) approach to finding a smaller sequence is
    to introduce the rule - no odd numbers. Quick pencil and paper
    calculations suggest that the sequence starting 2, 4, 6, 18, 20, 28 etc
    is going to increase far more slowly.
    
    Brian

        re .-1
        
>    Surely a better (the best?) approach to finding a smaller sequence is
>    to introduce the rule - no odd numbers. Quick pencil and paper
>    calculations suggest that the sequence starting 2, 4, 6, 18, 20, 28 etc
>    is going to increase far more slowly.
        
        4 is a square, so you can't use that.  The sequence
        
        	2, 6, 12, 20, 40, ...
        
        seems to work but is growing faster than the one you
        indicated.
        
        Dan

Here are the first few terms of a few of the suggested sequences.

If s_n is the smallest integer that preserves the square-free property,
2 3  5 10 27  38 120 258 907 2030 3225 8295 15850  80642 378295 1049868 3031570

If s_n is the smallest even integer that preserves the square-free property,
2 6 12 20 40 108 152 474 480 2560 5080 7846 43628 130612 259158 1064774 3559460

If s_n is the smallest integer such s_n+2 thru s1+...+s_n are between
consecutive squares (and the sequence starts 2 3 5),
2 3 5 24 288 25920 172160640 7412080583220480 13734735281170042526550640949760

(From Andrew Buchanan)

        There's nothing in the definition that restricts t_n from being the
*same* as t_(n-1).   But the series 2,3,5... seems to assume it.   If you
relax this constraint, you get:

2 3 3 5 21 24 24 80 80 80 480 480...

which seems to be growing much slower than any of the other sequences
explored.

Cheers,
Andrew.

 -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -
Subj:	a neat sequence for 1615

	Here's a sequence with the property that there is no non-empty subbag 
of the terms which sums to a square.   I think it would be quite difficult to 
show that each term is the smallest that can be chosen at each stage, (see 
note 1615) but it gives a specific growth rate that can be compared to other 
iteratively derived such sequences.

2 3 3 5 21 24 24
80 80 80 480 480 720 1200 2000 8400 9600 9600 
400*80 400*80 400*80 400*480 400*480 400*720 400*1200 400*2000 400*8400 
	400*9600 400*9600 
400�*80 400�*80 400�*80 400�*480 400�*480 400�*720 400�*1200 400�*2000 
	400�*8400 400�*9600 400�*9600
400�*80... etc.

	To see that no subbag of this sequence can sum to a square, first
consider the leading 7 terms.   All later terms are multiples of 80, so let's
look at subbags of {2,3,3,5,21,24,24}, and see which of those are quadratic
residues mod 80.   Spectacularly, {0} is the only available quadratic residue!
So 2 can contribute to no square, and we can lump all the others,
{3,3,5,21,24,24}, into a single term of size 80.

	Now, consider the sequence mod 400*80   All sufficiently late terms of
the sequence are multiples of this, so we need only examine:
{80, 80, 80, 80, 480, 480, 720, 1200, 2000, 8400, 9600, 9600}
We are looking for subbags of this which sum to a quadratic residue mod 32000.
Once again, we find that the only possible sum which is a quadratic residue
(mod 32000) is 0.   So, this lot can contribute only 0 or 32000 to a square.
So, we can lump say {480, 480, 200, 8400, 9600, 9600} into a single term of
size 400*80.

	But now, consider the sequence mod 400�*80.   It's clear that we can
continue in this way indefinitely, and therefore there is no subbag of terms
which sums to a non-zero square.

*******************************************************************************

	The growth rate of this sequence = 400^(1/11) ~= 1.724054174.

Cheers,
Andrew.

(From Andrew Buchanan)

	Here's a simpler sequence which uses the same principle to avoid
squares as my previous example.

2	2.4	2*4�	2*4�...

	Consider this sequence mod 4, etc.

	In fact, this is just one example of a more general idea.   Let p be
any prime.   Then, build the following sequence, written in a way so as to
make the recursive pattern clear.

p	p	...	p		[p-1 occurences of 'p']

p�	p�	...	p�		[then p-1 occurences of 'p�']

p^5	p^5	...	p^5		[then p-1 occurences of 'p^5']

...					[and so on]

	Considering this sequence mod p�, etc, it's clear that it can contain
no subbag that adds to a square.   Moreover the rate of growth of this sequence
is p^(2/p-1).   This can be made as close to unity as desired by taking p
sufficiently large.   The growth is still exponential, however.

	An open question is whether any sequence exists which is polynomial in
growth, but still does not admit a square as the sum of a subbag.

	Note that the sequence:
p	p�+p	2p�+p	...	(p-2)p�+p
p�	p^4+p�	2p^4+p�	...	(p-2)p^4+p�
p^5	p^6+p^5	2p^6+p^5...	(p-2)p^6+p^5
...
has the same growth rate as the sequence above, admits no squares as sum of
a subset, and all terms are distinct.

Cheers,
Andrew