[seqfan] Re: Two make a palindrome
Neil Sloane
njasloane at gmail.com
Tue Nov 12 11:03:06 CET 2013
In the binary case, if the smallest missing number N has an odd no of 1's
and an odd no of 0's, then from a certain point
on the sequence has to contain only numbers
with an even number of 0's and an even number of 1's.
(These are the numbers that won't "react" with N.)
Go out a long way in the sequence until we reach
a huge number of that type. By the rule
for constructing the sequence, the next term could be and so must be a
number with an odd no of 1's and an even no of 1's (or v.v.) (there are an
infinite number of them available,
but none appeared after step T). This is a contradiction.
This is the same argt. as in my first email.
The same argt. works in base 10, as I said.
Neil
On Tue, Nov 12, 2013 at 4:48 AM, Rob Arthan <rda at lemma-one.com> wrote:
> [Aside: thanks to Maximilian Hasler for checking my calculations and
> submitting A228407.]
>
> Neil,
>
> I am not sure I see how to complete your argument, but I do have an
> alternative that
> works in the base 2 case. See below:
>
> On 12 Nov 2013, at 06:20, Neil Sloane wrote:
>
> > I think one can show that every number must appear (in Eric's palindrome
> > sequence, in any base). Let me do the binary case
> > Remark: the only numbers that can't be rearranged to form
> > a palindrome are those with an odd number of 1's AND an odd number of
> 0's.
> >
> > Suppose N is the smallest number that never appears.
> > Suppose N has i 1's and j 0's. There are 4 cases
> > depending on the parity of i and j, but the argument is the same in each
> > case.
> >
> > It is easy to see that the sequence is infinite.
> >
> > Let it run for ever. After a while, after T steps, say, all the numbers
> > less than N that will ever appear have appeared. From now on every number
> > is bigger than N.
> > Suppose say that i is even and j is odd.
> > From now on, that is, from T steps on, every term must have an odd number
> > of 1's and an even number of 0's......... (*)
> > (Otherwise we could take the next term to be N , getting a number which
> is
> > not of the form odd no of 1's AND odd even no of 0's.)
> >
> > Take a large number M, a long way along in the sequence, of this form.
> The
> > next term after M could be - and so must be - a smallish number, just
> > bigger than N, with an even number of 0's and 1's. This will combine
> with M
> > to form a palindrome.
> > That contradicts (*).
> >
> This sounds plausible, but I am not sure I understand how to complete the
> argument.
> If N has odd numbers of both 0's and 1's, N will not react with an M with
> even numbers of both. How do we know we are not going to get an infinite
> sequence of numbers of the latter type?
>
> However, for base 2, we can be a bit more precise. A pattern emerges if
> you tabulate the first
> 34 values of n, a(n) and the smallest number that is missing from a(1) ..
> a (n)
> (call that m(n) say). Here they are with n in decimal and a(n) and m(n) in
> binary.
> I have put a * alongside the rows where n = 2^i+2 with i >= 3.
>
> 1: 0, 1
> 2: 11, 1
> 3: 1, 10
> 4: 10, 100
> 5: 100, 101
> 6: 111, 101
> 7: 1000, 101
> 8: 101, 110
> 9: 110, 1001
> * 10: 1001, 1010
> 11: 1010, 1011
> 12: 1100, 1011
> 13: 1111, 1011
> 14: 10000, 1011
> 15: 1011, 1101
> 16: 1101, 1110
> 17: 1110, 10001
> * 18: 10001, 10010
> 19: 10010, 10011
> 20: 10100, 10011
> 21: 10111, 10011
> 22: 11000, 10011
> 23: 11011, 10011
> 24: 11101, 10011
> 25: 11110, 10011
> 26: 100000, 10011
> 27: 10011, 10101
> 28: 10101, 10110
> 29: 10110, 11001
> 30: 11001, 11010
> 31: 11010, 11100
> 32: 11100, 11111
> 33: 11111, 100001
> * 34: 100001, 100010
>
> For each n of the form 2^i+2 for i >= 3, a(n) = n-1 and m(n) = n, so for
> these n
> a(1) .. a(n) is a permutation of the integers between 0 and n-1 and a(n)
> is the
> smallest (i+1)-bit number with an even number of 1s. Two numbers with the
> same
> number of bits react iff they both have an even number of 1s or both have
> an
> odd number of 1s. So what happens from 2^i+1 up to 2^(i+1)+1 is that you
> get all the (i+1)-bit numbers with an even number of 1s in increasing
> order,
> then 2^(i+1) (i.e., the smallest (i+2)-bit number with an odd number of 1s)
> and then all the (i+1)-bit numbers with an odd numbers of 1s in increasing
> order.
>
> > I think the same argument works in any base.
> > Let N be the smallest missing number.
> > Then all remaining numbers must be "non-reactive"
> > with respect to N. But there are infinitely many numbers
> > that will combine with N and after a while one of them
> > will be a candidate for the next term, getting a contradiction.
> >
>
> I don't see how to exclude the cases where the missing number N has an
> odd number of each of some subset of 2 or more of the digits and the
> sequence manages to avoid reacting with N indefinitely, e.g., by never
> including any of the digits that occur an odd number of times in N.
>
> I had to abandon my calculations in the base 10 case after a couple of
> days. m(n) had persisted at 1579 from n = 37475 up to 44681. So if
> m(n) does tend to infinity (i.e., if a(n) is a permutation of the
> integers),
> it seems to do so quite slowly for large bases.
>
> Regards,
>
> Rob.
>
> > Neil
> >
> >
> > On Mon, Nov 11, 2013 at 4:05 PM, Neil Sloane <njasloane at gmail.com>
> wrote:
> >
> >> Concerning the binary version, to get the ball rolling I added A230891
> and
> >> A230892.
> >> They need more terms, a b-file, some theorems, ...
> >>
> >>
> >> On Sun, Nov 10, 2013 at 9:12 AM, Neil Sloane <njasloane at gmail.com>
> wrote:
> >>
> >>> Maximilian said:
> >>> "I propose the sequence as https://oeis.org/draft/A228407 where I
> added a
> >>> link to Rob's post/calculations, and also a list of "records of
> >>> minima", i.e., (n,a(n)) where the least missing integers occur. Maybe
> >>> these could become sequences on their own (the values and the indices
> separately)
> >>> if further investigations in that sense are to be made."
> >>> Yes, that would be a very good idea - could you possibly add those two
> >>> sequences?
> >>> So here - like Recaman's A005132 - we have a sequence that may or may
> not
> >>> contain every number!
> >>> Thanks! Neil
> >>>
> >>>
> >>> On Sat, Nov 9, 2013 at 7:54 PM, Maximilian Hasler <
> >>> maximilian.hasler at gmail.com> wrote:
> >>>
> >>>> Rob, Eric, SeqFans,
> >>>> I propose the sequence as https://oeis.org/draft/A228407 where I
> added
> >>>> a link to Rob's post/calculations, and also a list of "records of
> >>>> minima", i.e., (n,a(n)) where the least missing integers occur. Maybe
> >>>> these could become sequences on their own (the values and the indices
> >>>> separately) if further investigations in that sense are to be made.
> >>>> Regards,
> >>>> Maximilian
> >>>>
> >>>>> Le 9 nov. 2013 à 17:10, "Rob Arthan" <rda at lemma-one.com> a écrit :
> >>>>>
> >>>>>> Eric,
> >>>>>>
> >>>>>> That's a fun sequence and an interesting conjecture. As you say, it
> >>>> is not easy to calculate by hand. To get a feel
> >>>>>> for the conjecture I wrote an ML program to do it. This is what I
> got
> >>>> for the first 200 values:
> >>>> (...)
> >>>>>> My program is now in a loop printing out n, a(n) and m(n). The
> >>>> evidence currently supports your conjecture but m(n) is
> >>>>>> growing quite slowly:
> >>>>>>
> >>>>>> a(5846) = 589, m(5846) = 598
> >>>>>> a(5847) = 598, m(5846) = 679
> >>>>>> ...
> >>>>>> a(11539) = 1617, m(11539) = 679
> >>>>>> a(11540) = 679 m(11540) = 697
> >>>>>>
> >>>>>> So 697 persisted as the smallest missing integer for more than 5,000
> >>>> stages. I will leave it running and report back if anything noteworthy
> >>>> occurs.
> >>>>>>
> >>>>>> Regards,
> >>>>>>
> >>>>>> Rob.
> >>>>>>
> >>>>
> >>>> _______________________________________________
> >>>>
> >>>> Seqfan Mailing list - http://list.seqfan.eu/
> >>>>
> >>>
> >>>
> >>>
> >>> --
> >>> Dear Friends, I have now retired from AT&T. New coordinates:
> >>>
> >>> Neil J. A. Sloane, President, OEIS Foundation
> >>> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> >>> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway,
> NJ.
> >>> Phone: 732 828 6098; home page: http://NeilSloane.com
> >>> Email: njasloane at gmail.com
> >>>
> >>>
> >>
> >>
> >> --
> >> Dear Friends, I have now retired from AT&T. New coordinates:
> >>
> >> Neil J. A. Sloane, President, OEIS Foundation
> >> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> >> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway,
> NJ.
> >> Phone: 732 828 6098; home page: http://NeilSloane.com
> >> Email: njasloane at gmail.com
> >>
> >>
> >
> >
> > --
> > Dear Friends, I have now retired from AT&T. New coordinates:
> >
> > Neil J. A. Sloane, President, OEIS Foundation
> > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> > Phone: 732 828 6098; home page: http://NeilSloane.com
> > Email: njasloane at gmail.com
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
--
Dear Friends, I have now retired from AT&T. New coordinates:
Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com
More information about the SeqFan
mailing list