[ March 1, 2022 ]
Sequence and patterns with n and φ(n) both palindromes
( phi(n) or φ(n) being the Euler totient function )
An exploration by Alexandru Petrescu (email)
Sequence with n and φ(n) both palindromes
φ(n) is the Euler totient function –
number of positive integers less than n, coprime with n.
Two numbers are said to be coprime if there are no
common factors other than 1.
I checked only numbers n having at least 2 digits,
because all one digit numbers have this property.
The data for n<109 are in the first table.
| # | n | φ(n) |
|---|
| 1 | 535 | 424 |
| 2 | 767 | 696 |
| 3 | 20502 | 6336 |
| 4 | 50805 | 27072 |
| 5 | 53035 | 42424 |
| 6 | 58085 | 46464 |
| 7 | 58585 | 46864 |
| 8 | 59395 | 40704 |
| 9 | 82428 | 27472 |
| 10 | 88188 | 29392 |
| 11 | 3269623 | 2747472 |
| 12 | 5808085 | 4646464 |
| 13 | 5846485 | 4473744 |
| 14 | 8110118 | 4050504 |
| 15 | 8666668 | 4053504 |
| 16 | 8818188 | 2939392 |
| 17 | 8872788 | 2957592 |
| 18 | 8875788 | 2958592 |
| 19 | 473040374 | 234414432 |
| 20 | 515050515 | 234414432 |
| 21 | 530303035 | 424242424 |
| 22 | 535353535 | 428282824 |
| 23 | 580303085 | 464242464 |
| 24 | 580858085 | 464686464 |
| 25 | 581585185 | 460040064 |
| 26 | 585797585 | 466535664 |
| 27 | 593939395 | 407272704 |
| 28 | 615272516 | 291444192 |
| 29 | 702696207 | 405909504 |
| 30 | 881242188 | 293747392 |
| 31 | 887848788 | 295949592 |
Some remarks over this data:
- First conjecture: n has an odd number of digits.
- Second conjecture: the sequence is infinite.
- It’s interesting to note that the pair (marked by orange colour)
with two different numbers having the same value!
The two values for n are coprime.
- There are some patterns for n ∧ φ(n) - see second table
(index notation for number of repeating sequence)
| # | n | φ(n) |
|---|
| 1 | 535 | 424 |
| 2 | 535353535 | 428282824 |
| 3 | 5353535353535 | 4282828282824 |
| 4 | 5(35)34 | 4(28)3324 |
| 1 | 88188 | 29392 |
| 2 | 8818188 | 2939392 |
| 1 | 535 | 424 |
| 2 | 53035 | 42424 |
| 3 | 530303035 | 424242424 |
| 1 | 58085 | 46464 |
| 2 | 5808085 | 4646464 |
And so on
The following Pari/gp program (by PDG) recreates
the solutions from the first table and more. It builds
on the assumation that Alexandru's conjecture is true
and that there are only n's with odd number of digits.
Nextpalodd(k)= \
n=digits(k); le2=length(n)\2; \
swl=digits(fromdigits(n[1..le2+1])+1); m=fromdigits(concat(swl,Vecrev(swl[1..le2]))); \
return(m);
{
k=100; cnt=0;
for(i=1,oo,
Nextpalodd(k); k=m; ned=digits(eulerphi(m));
if(Vecrev(ned)==ned, cnt+=1; print(cnt," ",m," ",eulerphi(m)) );
if(i%100000==0, print1(k,Strchr(13)) );
);
}
The last line could be deleted if you're not interested in the progress.
It also saves some running time.
Within 5 minutes you get the 89th term of the sequence.
A000215 