# [seqfan] Re: Digital question; a question about the palindromes

Robert Israel israel at math.ubc.ca
Thu Mar 3 18:35:35 CET 2011


On Thu, 3 Mar 2011, Robert Israel wrote:

> For example, two-digit (b,c)-palindromes satisfy b a_1 + a_2 = c a_2 + a_1,
> i.e. (b - 1) a_1 = (c - 1) a_2, or a_1/a_2 = (c-1)/(b-1).  Nontrivial
> examples will require gcd(c-1,b-1) > 1.
> For example, 45_11 = 54_9 = 49.
>
> Three-digit (b,c) palindromes satisfy
> (b^2-1) a_1 + (b-c) a_2 + (c^2-1) a_3 = 0.

Of course that should have been
(b^2-1) a_1 + (b-c) a_2 - (c^2 - 1) a_3 = 0.
This typo doesn't affect the rest of the message.

>  If c=b+1 this becomes
> a_2 = (b^2-1) a_1 - (b^2 + 2b) a_3.  But then a_2 == -a_1 mod b, so
> a_2 = b - a_1, and then a_1 = a_3 + (1 + 2 a_3)/b.  With 0 <= a_3 < b,
> this can only happen if b = 1 + 2 a_3.  Thus we have three-digit
> (2n+1, 2n+2) palindromes (n+1,n,n)_{2n+1} = (n,n,n+1)_{2n+2}, e.g.
> 544_9 = 445_10.
>
>
> Robert Israel                                israel at math.ubc.ca
> Department of Mathematics        http://www.math.ubc.ca/~israel University of
> British Columbia            Vancouver, BC, Canada
>
> On Thu, 3 Mar 2011, Vladimir Shevelev wrote:
>
>>      Let base-b of n is [a_1...a_k]_b. Consider base-c reverse: [a_k...a_1]
>> _c.
>> If  [a_1...a_k]_b= [a_k...a_1] _c, then n is called (b,c)-palindromic.
>> E.g., n=0 and n=1 are (b,c)-palindromic for every b,c. On the other hand,
>> nontrivial (b,c)-palindromes could exist when the ratio b/c is closed to 1,
>> e.g., c=b+1 for sufficiently large b.
>>     I ask anyone to find some of them.
>>
>> This problem arose from David's digit question and the following its
>> generalization:
>> d | n= [a_1...a_k]_b <=>d | [a_k...a_1] _c <=>d | bc-1
>> which one can prove by same way.
>> The case b=c corresponds to David's observation.
>> Palindromes arose in my last message on this topic.
>>
>> Regards,
>>
>> ----- Original Message -----
>> From: Vladimir Shevelev <shevelev at bgu.ac.il>
>> Date: Friday, February 25, 2011 22:34
>> Subject: [seqfan] Re: Digital question
>> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>>
>>> Let us separate a nontrivial part of your proof,
>>>
>>> If inv(d)<d, then it is sufficient to choose n=d ; if
>>> inv(d)>d and not multiple of d, then n=d is required as well.
>>> What is the left? d could be either PALINDROMIC (inv(d)=d)
>>> or a number wth the reversal  multiple of d (cf.
>>> A031877).  Denote the set of such numbers R_b.
>>>
>>> Thus from your proof we conclude that, if d is not a divisor of
>>> b^2-1, then, for every d \in R_b, there exists  m such that
>>> m*d is not only in R_b but even inv(m*d) is not multiple of d.
>>>
>>>    Maybe, there exists a direct proof of this fact?
>>>
>>> Thanks,
>>>
>>>
>>> ----- Original Message -----
>>> From: Juan Arias de Reyna <arias at us.es>
>>> Date: Thursday, February 24, 2011 10:59
>>> Subject: [seqfan] Re: Digital question
>>> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>>>
>>>> Here is the proof of
>>>>
>>>>  (d does not divide b^2-1) => there exists n with d | n
>>> but
>>>> not d | n_1.
>>>>
>>>>
>>>>
>>>> Assume that (d does not divide b^2-1)   we want to
>>>> prove that there exists n with
>>>> d | n but not d | n_1.
>>>>
>>>> (a) We may assume that  gcd(d,b)=1. In other
>>>> case   d = d_1*d_2 with  gcd(d_1,b)=1
>>>> d_2 | b^k  for a suitable k.   Now  (d_1
>>>> does not divide b^2-1)    and if we find
>>>> n with  d_1 | n but not d_1 | n_1.  Take
>>>> m=n*b^k  it is clear that d | m   and
>>>> m_1 = n_1, so that d does not divide m_1.
>>>>
>>>>
>>>> (b) Let  e the least natural number with  d | b^e-
>>>> 1.  We will have e > 2, since
>>>> d does not divide b^2 -1 and hence also does not divide b-1.
>>>>
>>>> Let x_0=1, x_1, x_2,  x_{e-1} , defined by x_j is the
>>> rest
>>>> of b^j mod d.
>>>> The usual criterion of divisibility gives us  d | n is
>>>> equivalent to
>>>> d | A_0+A_1*x_1+A_2*x_2+ ... + A_{e-1}*x_{e-1} where if
>>>> A_j = a_j+a_{j+e}+a_{j+2e}+...
>>>> are the sum of the digits of the representation of n in base b.
>>>>
>>>> Given elements (z_j)_{j=0}^{e-1} in Z/(dZ) it is easy to
>>>> construct a number n such that
>>>> A_j(n)\equiv z_j mod d  and  A_j(n_1) equiv z_{e-j-
>>> 1}
>>>> mod d.  Therefore we only need to construct
>>>> elements z_j in Z/(dZ) such that  z_0+z_1*x_1+z_2*x_2+
>>> ...
>>>> + z_{e-1}*x_{e-1}=0 and
>>>> z_{e-1}+z_{e-2}*x_1+z_{e-3}*x_2+ ... + z_{0}*x_{e-1} != 0
>>>>
>>>>
>>>>
>>>> Assume that e is odd. e = 2f+1  then take  z_0 =
>>>> 0,  z_f = -b^f, z_{e-1}=1 and all other
>>>> z_j = 0. Then
>>>>
>>>> z_0+z_1*x_1+z_2*x_2+ ... + z_{e-1}*x_{e-1} = -b^f x_f+x_{2f} =
>>> -
>>>> b^f b^f + b^(2f) = 0
>>>> and
>>>> z_{e-1}+z_{e-2}*x_1+z_{e-3}*x_2+ ... + z_{0}*x_{e-1} =1 - b^f
>>>> x_f = 1-b^(2f) != 0
>>>> since b^e = b^(2f+1) is the first power of b  equal to 1.
>>>>
>>>> Assume now that e is even  e = 2f. Since e >2  we
>>>> have  e >= 4.
>>>> In this case take  z_0 = -b^f, z_{f-1} = b, z_f =
>>> 0,
>>>> z_{2f-1}=0. Then we will have
>>>> z_0+z_1*x_1+z_2*x_2+ ... + z_{e-1}*x_{e-1} = -b^f + b x_{f-1}
>>> = -
>>>> b^f + b^f = 0
>>>> and
>>>> z_{e-1}+z_{e-2}*x_1+z_{e-3}*x_2+ ... + z_{0}*x_{e-1} = b x_f -
>>>> b^f x_{e-1} =
>>>> b^(f+1) - b^f b^(2f-1) = b^(f+1) - b^(f-1) = b^(f-1) (b^2-1)
>>> != 0.
>>>>
>>>> This ends the proof.
>>>>
>>>> Regards,
>>>> Juan Arias de Reyna
>>>>
>>>>
>>>> El 23/02/2011, a las 01:05, David Wilson escribiÃ³:
>>>>
>>>>> Very good. Now show
>>>>>
>>>>> (d does not divide b^2-1) => there exists n with d | n but
>>> not
>>>> d | n_1.
>>>>>
>>>>>
>>>>> ----- Original Message ----- From: "Vladimir Shevelev"
>>>> <shevelev at bgu.ac.il>> To: "Sequence Fanatics Discussion
>>> list"
>>>> <seqfan at list.seqfan.eu>> Sent: Tuesday, February 22, 2011
>>>> 7:33 AM
>>>>> Subject: [seqfan] Re: Digital question
>>>>>
>>>>>
>>>>>> From b^(t-1)*n-n_1==0 (mod d) we conclude that d | n => d |
>>>> n_1. Since {n_1 is inv. n}<=>
>>>>>> {n is inv. n_1}, then also b^(t-1)*n_1-n==0 (mod d) and we
>>>> conclude that d | n_1 => d | n.
>>>>>>
>>>>>> Regards,
>>>>>
>>>>>
>>>>>
>>>>> -----
>>>>> No virus found in this message.
>>>>> Checked by AVG - www.avg.com
>>>>> Version: 10.0.1204 / Virus Database: 1435/3459 - Release
>>> Date:
>>>> 02/22/11>
>>>>>
>>>>> _______________________________________________
>>>>>
>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>>>
>>>> _______________________________________________
>>>>
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>>
>>>
>>> _______________________________________________
>>>
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>