[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

139.0. "In base 3 out base 2" by HARE::STAN () Fri Aug 24 1984 19:57

Here is a sequence with an interesting property that I heard about
at a talk by Dave Roselle (at the MAA Summer meeting in Eugene Oregon):

Start with the numbers 0 and 1.  Then continue the sequence with
successive integers, but avoid adding any integers that would cause
the sequence to contain a 3-term arithmetic progression.  Thus you can't
put 2 next since 0,1,2 is an arithmetic progression. So 3 comes next,
then 4. But you can't put 5 since 1,3,5 is an arithmetic progression,
and you can't put 6 next since 0,3,6 is an arithmetic progression, etc.
The sequence begins

	0, 1, 3, 4, 9, 10, 12, 13, 27, 28, ...

There turns out to be another neat characterization of this sequence
(proof left up to the reader):

Write down the integers in base 3 that do not contain the digit 2.
Then interpret these digit strings as binary numbers, and you get the
above-mentioned sequence!

Number (decimal)	Base 3 representation

	 0			0000
	 1			0001
	 3			0010
	 4			0011
	 9			0100
	10			0101
	12			0110
	13			0111
	27			1000
	28			1001

		etc.
T.RTitleUserPersonal
Name		DateLines
139.1TAV02::NITSANMon Oct 08 1984 17:5215
 Define A as the set of all numbers whose base 3 representation contains
0's and 1's only:  A = { 0 , 1 , 10 , 11 , 100 , 101 , ... } (base 3)

 Summing any TWO numbers from A you'll NEVER have any CARRY (base 3), for
obvious reasons. So, Summing two DIFFERENT numbers, the sum must contain
the digit "1" (base 3...). On the other hand, Summing two EQUAL numbers
(multiplying by 2), the sum is made of "0" and "2" only. Therefore, no number
from A is the mean (average) of two others (= no 3-term arith. prog.)

 A is "maximal" because if you put "xxx2xxx" in it, you'll get your 3-term
a.p. with "xxx0xxx","xxx1xxx","xxx2xxx".

                                    Nitsan Duvdevani

  (...well you said not to be bashful...)
139.2TURTLE::GILBERTMon Oct 08 1984 17:0115
Nice work!

I tried starting the sequence with 1 or 2, and quickly realized that it simply
added 1 or 2 to every number in the sequence.

Consider a similar problem, except that 3-element arithmetic progressions are
allowed (eg: a, a+b, a+2b), but 4-number arithmetic progressions are disallowed
(eg: a, a+b, a+2b, a+3b).  This sequence begins:

0,1,2,4,5,7,8,9,14,15,16,18,25,26,28,29,30,33,36,48,49,50,52,53,55,56,57,62,64

(this ought to be checked "by machine").  Note that sequences of 3 consecutive
numbers appear several times.  Is there a pattern?

					- Gilbert
139.3TAV02::NITSANTue Oct 09 1984 15:0312
 Doesn't look like it, but if you take one more step to disabling 5-number
arithmetic progressions, and display results in base 5, you'll get ALL numbers
that DO NOT USE THE DIGIT "4" !

 You see, if you add the same "b" four times (suppose gcd(b,5)=1) then you get
a permutation of 0,1,2,3,4 mod 5, which means you pass through 4 mod 5. If the
gcd is not 1 (for example: a,a+10,a+20,a+30,a+40), you pass through the digit
"4" in higher "base 5 locations"...

 This is not true for 4-number a.p. and base 4, because "4" is not PRIME, so
you get sequences like 2,4,6,8 (2,10,12,20 base 4). I know this is not "the
formal proof" but it's just came out as I looked at it...    (NITSAN)X