|
Ulam s-Additive Sequences
Let s be a positive integer. A strictly increasing sequence of positive
integers
is s-additive [1,2] if, for ,
is the least integer exceeding
which has precisely s representations
The first terms of an s-additive
sequence are called the base of the sequence. An s-additive sequence,
for a given base, may be either finite or infinite; we assume the sequence
is maximal in the sense that the total number of terms is as large as
possible.
Here are three open problems (among many) associated with s-additive
sequences. The first is well-known; the other two deserve more attention.
1.Consider the s-additive sequence with .
The next fifteen terms of the sequence are
3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53
and more are given here. The sequence is infinite
(as is any 1-additive sequence) since
is an integer greater than with no
other representation and, hence,
there exists a least such integer. It is the archetypal s-additive
sequence and was first studied by Ulam [3].
Open Problem: does Ulam's sequence have zero asymptotic density
(relative to the positive integers)?
2.Consider the 1-additive sequence with
and for some integer
. It appears to be true that the
only even terms in this sequence are
although a proof is not known. Computations show that
the sequence for m=3 is regular in the
sense that the sequence of sucessive differences
is eventually periodic. Moreover, when m=3, the smallest positive integer
N such that
for all sufficiently large n is .
This integer N is called the period of the sequence. The
fundamental difference of the sequence is likewise defined to be
for large enough n, and thus the asymptotic density of the sequence
is positive (in particular).
Open Problem: what are the values of N and D for
the sequence for m=4?
Hint: use the fact that the number of even terms is (evidently)
finite to build an efficient, low-memory algorithm for computing
. Much more has been proved
concerning the two (somewhat easier) cases:
and
References [1-7] should be consulted for details.
3.Consider the 2-additive sequence with
. The next fifteen terms of the
sequence are
5, 6, 8, 10, 12, 15, 17, 19, 29, 31, 33, 43, 44, 47, 51
and more are given here.
Open Problem: is this sequence infinite?
I suspect that the third problem is very hard, but the second problem
should yield to some clever individual with enough computing power and
patience to spare! Interested readers are urged to examine [1-7] as well
as essays on the
Stolarsky-Harborth constant
and
quadratic recurrence constants.
References
- R. Queneau, Sur les suites s-additives,
J. Combin. Theory Ser. A. 12 (1972) 31-71;
MR 46 #1741.
- S. Finch, Conjectures about 1-additive sequences,
Fibonacci Quart. 29 (1991) 209-214;
MR 92j:11009.
- R. K. Guy, Unsolved Problems in Number Theory, 2nd ed.,
Springer-Verlag, 1994, section C4;
MR 96e:11002.
- S. Finch, On the regularity of certain 1-additive sequences,
J. Combin. Theory Ser. A. 60 (1992) 123-130;
MR 93c:11009.
- S. Finch, Patterns in 1-additive sequences,
Experim. Math. 1 (1992) 57-63;
MR 93h:11014.
- J. H. Schmerl and E. Spiegel, The regularity of some 1-additive sequences,
J. Combin. Theory Ser. A. 66 (1994) 172-175;
MR 95h:11010.
- J. Cassaigne and S. Finch, A class of 1-additive sequences and
quadratic recurrences,
Experim. Math. 4 (1995) 49-60;
MR 98c:11010.
Copyright © 1995-2001 by Steven Finch.
All rights reserved.
|