Base-10 Skolem-Langford numbers
Dean Hickerson
dean at math.ucdavis.edu
Tue Aug 28 04:48:02 CEST 2007
Hans Havermann wrote:
> Conjecture: Half the sum of the digits of these numbers is even.
>
> The conjecture is trivially true in the sense that I can verify it
> for all 20120 terms. However, I wonder if someone has a simple proof
> of it.
A108116 is only finite because of the artificial constraint that the
digits be <= 9. In fact Hans's conjecture is true more generally, not
just for those cases.
Theorem: Suppose {a_1, ..., a_(2n)} is a sequence of nonnegative integers
such that (A) any number which occurs in the sequence occurs exactly twice
and (B) if a_i and a_j (i<j) are the two occurrences of the number d, then
j-i=d+1. Then a_1 + a_2 + ... + a_(2n) is a multiple of 4.
Proof: Let D be the set of numbers that occur in the sequence; D has
exactly n elements. For each d in D, let l(d) and r(d) be the smallest
and largest indices i such that a_i = d; we have r(d)-l(d) = d+1. Let
s be the sum of the elements of D.
(For example, for the sequence 15120025, we have n=4, D={0,1,2,5}, s=8,
and l and r are given by this table:
d l(d) r(d)
0 5 6
1 1 3
2 4 7
5 2 8 )
Note that
SUM (r(d) - l(d)) = SUM (d+1) = s + n
d in D d in D
Also, every number from 1 to 2n occurs exactly once as either l(d) or r(d), so
SUM (r(d) + l(d)) = 1 + 2 + ... + 2n = 2 n^2 + n
d in D
The difference between these two sums is twice the sum of l(d), so it's
even; hence s is even. The sum a_1 + a_2 + ... + a_(2n) equals 2s,
so it's divisible by 4.
Dean Hickerson
dean at math.ucdavis.edu
More information about the SeqFan
mailing list