[seqfan] Re: Digital question; a question about the palindromes
Robert Israel
israel at math.ubc.ca
Thu Mar 3 17:27:35 CET 2011
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. 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,
> Vladimir
>
> ----- 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,
>> Vladimir
>>
>>
>> ----- 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,
>>>>> Vladimir
>>>>
>>>>
>>>>
>>>> -----
>>>> 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/
>>>
>>
>> Shevelev Vladimir
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
> Shevelev Vladimir
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list