[seqfan] Re: Digital question; a question about the palindromes
Vladimir Shevelev
shevelev at bgu.ac.il
Thu Mar 3 12:36:36 CET 2011
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
More information about the SeqFan
mailing list