World!Of
Numbers

WON plate
215 |

[ 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)
1535424
2767696
3205026336
45080527072
55303542424
65808546464
75858546864
85939540704
98242827472
108818829392
1132696232747472
1258080854646464
1358464854473744
1481101184050504
1586666684053504
1688181882939392
1788727882957592
1888757882958592
19473040374234414432
20515050515234414432
21530303035424242424
22535353535428282824
23580303085464242464
24580858085464686464
25581585185460040064
26585797585466535664
27593939395407272704
28615272516291444192
29702696207405909504
30881242188293747392
31887848788295949592

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)
1535424
2535353535428282824
353535353535354282828282824
45(35)344(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 Prime Curios! Prime Puzzle
Wikipedia 215 Le nombre 215
```

```