[seqfan] Re: Two make a palindrome
Rob Arthan
rda at lemma-one.com
Tue Nov 12 10:48:13 CET 2013
[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/
More information about the SeqFan
mailing list