18
$\begingroup$

Let $\phi(n)$ be Euler's totient function. For $n=4m$ what is the smallest $n$ for which

$$\phi(n) \ne \phi(k) \textrm{ for any } k

When $n=4m+1$ and $n>1$ the smallest is $n=5$ and when $n=4m+3$ it's $n=3.$ However, when $n=4m+2$ the above condition can never be satisfied since

$$\phi(4m+2) = (4m+2) \prod_{p | 4m+2} \left( 1 - \frac{1}{p} \right)$$ $$ = (2m+1) \prod_{p | 2m+1} \left( 1 - \frac{1}{p} \right) = \phi(2m+1).$$

In the case $n=4m,$ $n=2^{33}$ is a candidate and $\phi(2^{33})=2^{32}.$ This value satisfies $(1)$ because $\phi(n)$ is a power of $2$ precisely when $n$ is the product of a power of $2$ and any number of distinct Fermat primes:

$$2^1+1,2^2+1,2^4+1,2^8+1 \textrm{ and } 2^{16}+1.$$

Note the $n=2^{32}$ does not satisfy condition $(1)$ because the product of the above Fermat primes is $2^{32}-1$ and so $\phi(2^{32})=2^{31}=\phi(2^{32}-1)$ and $2^{32}-1 < 2^{32}.$

The only solutions to $\phi(n)=2^{32}$ are given by numbers of the form $n=2^a \prod (2^{x_i}+1)$ where $x_i \in \lbrace 1,2,4,8,16 \rbrace $ and $a+ \sum x_i = 33$ (note that the product could be empty), so all these numbers are necessarily $ \ge 2^{33}.$

Why don't many "small" multiples of $4$ satisfy condition $(1)$? Well, note that for $n=2^a(2m+1)$ we have

$$\phi(2^a(2m+1))= 2^a(2m+1) \prod_{p | 2^a(2m+1)} \left( 1 - \frac{1}{p} \right)$$ $$ = 2^{a-1}(2m+1) \prod_{p | 2m+1} \left( 1 - \frac{1}{p} \right) = 2^{a-1}\phi(2m+1),$$

and so, for $a \ge 2,$ if $2^{a-1}\phi(2m+1)+1$ is prime we can take this as our value of $k and we have $\phi(n)=\phi(k).$ This, together with the existence of the Fermat primes, seems to be why it's difficult to satisfy when $n=4m.$

I have only made hand calculations so far, so I would not be too surprised if the answer is much smaller than my suggestion. The problem is well within the reach of a computer, and possibly further analysis without the aid of a computer. But, anyway, I've decided to ask here as many of you have ready access to good mathematical software and I'm very intrigued to know whether there is a smaller solution than $2^{33}.$

Some background information:

This question arose in my search to bound the function $\Phi(n)$ defined as follows.

Let $\Phi(n)$ be the number of distinct values taken on by $\phi(k)$ for $1 \le k \le n.$ For example, $\Phi(13)=6$ since $\phi(k)$ takes on the values $\lbrace 1,2,4,6,10,12 \rbrace$ for $1 \le k \le 13.$

It is clear that $\Phi(n)$ is increasing and increases by $1$ at each prime value of $n,$ except $n=2,$ but it also increases at other values as well. For example, $\Phi(14)=6$ and $\Phi(15)=7.$

Currently, for an upper bound, I'm hoping to do better than $\Phi(n) \le \lfloor (n+1)/2 \rfloor .$

But this this not the issue at the moment, although it may well become a separate question.

This work originates from this stackexchange problem.

  • 0
    I checked up to 10^7 and found no examples. I'll run something overnight and see how far it gets.2011-02-01
  • 0
    Shoot: Pari/GP has a bound on vectors somewhere less than 1.7x10^7. I'll have to use a different method.2011-02-01
  • 0
    I wrote a quick program to compute some values of your function ($\Phi$ that is). It seems like you should certainly be able to get a better lower bound. I've computed into the twenty thousands and the ratio of the terms appears to be approaching 1/5 for instance $\Phi(25000)=5032$. It may be going lower, I'll let it run over night and see how far it gets. It may actually be slowing down more now that I look at a few values.2011-02-01
  • 0
    @Matthew: Thanks for that! It makes me glad that I decided to give up on the hand calculations, post the question and go to bed. Please let me know if your program finds a solution. Thanks.2011-02-01
  • 0
    @Jacob: Thanks for your time. I, too, think that a better lower bound than that implied by the PNT should be within reasonable reach, but I haven't yet given much thought to that side. My question arose when I was looking at the upper bound. Thanks for posting those numbers. I'm still trying to understand the behaviour of $\Phi(n),$ so please let me know if you have any further interesting results. Thanks.2011-02-01
  • 0
    Well over night my program calculated up to 270000 where the value of Phi was 47085. So it seems like the ratio between terms is still decreasing since that was (.17438).2011-02-01
  • 0
    This paper might be useful: http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.pjm/11028066402011-02-01
  • 0
    @Jacob: That raises some questions, but I'll keep my thoughts quite for the moment until I've had more time to think about the lower bound. Many thanks for the update.2011-02-01
  • 0
    @Matthew: Thanks for the reference. It was not a paper that I was aware of and, as you say, it could be useful.2011-02-01
  • 0
    @Jacob Schlather: If your program ran overnight to get to 270000, you might glean some ideas for optimization from the Java code I posted along with the answer ;-)2011-02-14

1 Answers 1

12

The answer is

\[33817088 = 2^9 \cdot 257^2 = 2^9 \cdot (2^8 + 1)^2\]

with

\[\phi(33817088) = 16842752 = 2^{16} \cdot (2^8 + 1) = 2^{16} \cdot 257\;.\]

Here's the Java code to find it (it takes a couple of seconds to run on a MacBook Pro):

import java.util.Arrays;  public class Totient {     final static int mod4 = 0;     // remainder mod 4 to test                                                                                                                                                                                                                           final static int n = 40000000; // highest number to test                                                                                                                                                                                                                             static boolean [] prime = new boolean [n / 2]; // prime [i] : is 2i + 1 prime?                                                                                                                                                                                                      static boolean [] seen = new boolean [n];      // seen [i] : we've seen phi (n) = i                                                                                                                                                                                                 static int [] phi = new int [n];               // phi [i] : phi (i)                                                                                                                                                                                                                  public static void main (String [] args) {         Arrays.fill (prime,true);         Arrays.fill (seen,false);         Arrays.fill (phi,1);          // calculate the primes we need                                                                                                                                                                                                                                                     int limit = (int) Math.sqrt (n); // highest factor to test                                                                                                                                                                                                                          for (int p = 3;p <= limit;p += 2) // loop over odd integers                                                                                                                                                                                                                             if (prime [p >> 1])            // only test primes p                                                                                                                                                                                                                                    for (int k = 3*p;k < n;k += 2*p) // loop over odd multiples of p                                                                                                                                                                                                                        prime [k >> 1] = false;      // sieve them out                                                                                                                                                                                                                           // fill phi by looping over all primes                                                                                                                                                                                                                                              fill (2);         for (int p = 3;p < n;p += 2)             if (prime [p >> 1])                 fill (p);          // now go through phi, remembering which values we've already seen                                                                                                                                                                                                                  for (int i = 1;i < n;i++) {             if ((i & 3) == mod4 && !seen [phi [i]]) {                 System.out.println ("found " + i + " with phi (" + i + ") = " + phi [i]);                 return;             }             seen [phi [i]] = true;         }     }      // multiply all phi values by their factors of prime p                                                                                                                                                                                                                              static void fill (int p) {         // once for the first factor of p                                                                                                                                                                                                                                                   for (int i = p;i < n;i += p)             phi [i] *= p - 1;          // and then for the remaining factors                                                                                                                                                                                                                                               long pow = p * (long) p; // long to avoid 32-bit overflow                                                                                                                                                                                                                           while (pow < n) {             for (int i = (int) pow;i < n;i += pow)                 phi [i] *= p;             pow *= p;         }     } } 
  • 0
    Sure but finding an answer that only tells us a the value asked for quite easy with access to the computational power of java, this does not qualify as an answer in the mathematics community albeit with *some* explanations of how the code works, it's necessary to describe things in a more formal manner with regard to how an answer in mathematics should be presented.2018-09-28
  • 1
    @Adam: I disagree (along with $11$ upvoters and the OP who marked this as the accepted answer, all of whom are members of this mathematics community just like you). There are many questions on this site that no one was able to answer without a computer and that I answered using a computer. I agree that any mathematics required to write or understand the code should be explained, but in the present case I used nothing more than well-known basic facts about Euler's totient function.2018-09-29
  • 0
    So what you are saying is that the use of a formalized system of notation for the purpose of allowing clarity for the student, is something of no value, and rather than me eventually concede defeat and learn how to write everything in latex so it renders into an image that uses the aforementioned system of notation, I should have defiantly invented my own programming language, cut and paste the source code, give any numerical value asked for and call it QED?2018-09-29
  • 1
    @Adam: No, that's not what I'm saying, those are your words. I was merely replying to your claim that "this does not qualify as an answer" and arguing that it does.2018-09-29
  • 0
    Not in the mathematics SE community I am afraid I still feel with all due respect sir. Yes it no doubt it is very cunning use of what I can only assume to be java, it's the language I used to use during the period I used the open source IDE from processing.org anyway as far as a novice like myself can see, I am not suggesting that your answer is inferior to that which could be presented in formal mathematics notation no, the principle doesn't change if said it in Spanish, C, php, maple code, etc but for the sake of the readers being directed here2018-09-29
  • 0
    To specifically learn things in mathematics, it means that not presenting it in a unified way results in the unnecessary layer of abstraction caused by presentation of answers in many differing programming languages, natural languages, do you understand where I am coming from now?2018-09-29
  • 1
    @Adam: Unfortunately I don't. This is a computer programme. It would make no sense to express it in mathematical form; I'm not even sure what exactly you mean by that. The purpose of including the programme isn't to convey mathematics, but rather that people can also run the programme or check or expand or fix it or whatever; all of this only works if I include it as a programme. The mathematics behind the programme is trivial; you can read up on it at Wikipedia; it's basically $\phi(\prod_ip_i^{k_i})=\prod_ip_i^{k_i-1}(p_i-1)$. And I do think the upvotes and the checkmark indicate acceptance.2018-09-29
  • 0
    Well I suppose it all depends on what your conditions for acceptance are, right? Absolutely that is what is intended to be implied, but it's not the type of subject for which the popular vote carries any real weight, It's not like there is direct proportion to the level of insight demonstrated in a post and the number of upvotes it receives.2018-09-29
  • 1
    @Adam: Of course not. "Level of insight" isn't a relevant category here. A question was asked, and I answered it. If you'd written "Posting a programme doesn't demonstrate any insight", I would have fully agreed. That's not what you wrote, though. You wrote "this does not qualify as an answer". It does, and $11$ people agree with me on that. If you don't agree, you can downvote.2018-09-30