Is the function $f(n)=\varphi(n)+\varphi(n+1)-n$ surjective?

167 Views Asked by At

For every positive integer $n$ define $$f(n)=\varphi(n)+\varphi(n+1)-n$$ $\varphi(n)$ denotes the totient-function.

Is $f(n)$ surjective on the non-negative integers ?

The first non-negative integer $k$ for which I yet did not find a positive integer $n$ with $f(n)=k$ is $k=998$. If there is no solution of $f(n)=998$, how can it be proven ?

1

There are 1 best solutions below

0
On BEST ANSWER

Below are the numbers up to 1000, along with 998, that cannot be represented with any $n \leq 100000.$ It would appear that there is little hope for a proof by inequalities, we keep getting larger and larger numbers $n$ such that $\phi(n) + \phi(n+1) - n$ is one of these.

jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$ date
Wed Jan 23 12:24:02 PST 2019
jagy@phobeusjunior:~$ ./mse 
    473     138855 = 3 * 5 * 9257           138856 = 2^3 * 17 * 1021
    774     403490 = 2 * 5 * 157 * 257           403491 = 3 * 11 * 12227
    206     435714 = 2 * 3 * 101 * 719           435715 = 5 * 7 * 59 * 211
    774     736434 = 2 * 3^2 * 163 * 251           736435 = 5 * 7 * 53 * 397
    539     2301765 = 3 * 5 * 173 * 887           2301766 = 2 * 17 * 67699
    774     2493914 = 2 * 43 * 47 * 617           2493915 = 3 * 5 * 53 * 3137
    473     2778215 = 5 * 11 * 50513           2778216 = 2^3 * 3 * 7 * 23 * 719
    206     2915474 = 2 * 19 * 73 * 1051           2915475 = 3 * 5^2 * 38873
    473     3063423 = 3 * 11 * 92831           3063424 = 2^7 * 7 * 13 * 263
    774     4182954 = 2 * 3 * 31 * 43 * 523           4182955 = 5 * 7 * 119513
    774     4372794 = 2 * 3^2 * 29 * 8377           4372795 = 5 * 7 * 101 * 1237
    158     5075570 = 2 * 5 * 507557           5075571 = 3 * 17 * 23 * 4327
    206     5357090 = 2 * 5 * 535709           5357091 = 3 * 17 * 23 * 4567
    774     6368810 = 2 * 5 * 7 * 37 * 2459           6368811 = 3 * 2122937
    158     38029730 = 2 * 5 * 29 * 71 * 1847        38029731 = 3 * 17 * 79 * 9439
    774     39871314 = 2 * 3^2 * 7 * 316439        39871315 = 5 * 11^2 * 59 * 1117
progress    50000000
Wed Jan 23 12:56:43 PST 2019

    158     64981730 = 2 * 5 * 11 * 47 * 12569      64981731 = 3 * 37 * 149 * 3929
    473     79627911 = 3 * 11 * 389 * 6203        79627912 = 2^3 * 7 * 13 * 109379
progress    100000000
Wed Jan 23 13:47:31 PST 2019

    206     121764914 = 2 * 17 * 3581321         121764915 = 3^2 * 5 * 137 * 19751
    158     145708130 = 2 * 5 * 53 * 89 * 3089 145708131 = 3 * 19 * 47 * 137 * 397
progress    150000000
Wed Jan 23 14:51:08 PST 2019

    473     194010879 = 3 * 239 * 270587        194010880 = 2^8 * 5 * 7 * 59 * 367
progress    200000000
Wed Jan 23 16:02:15 PST 2019