Numbers $n$ such that $n!$ has all of its exponents odd

63 Views Asked by At

(First paragraph for motivation, second paragraph the actual problem)

I usually have to be on a stand as an embassador for my major (math) for highschoolers, and we usually have problems written on a whiteboard for the kids to try. One of my favorite problems to pose, is whether $50!$ is a square, the idea being that $29$ only appears one time on its prime decomposition (or any prime $26\leq p\leq50$ for that matter). Of course, provided that one knows Bertrand's postulate, this is really easy for arbitrary $n$. But the other day, a kid showed that actually $13$ only appears $3$ times therefore it can't be a prime. So this got me to the following question:

Is there an $n$ relatively big, let's say, greater than $20$ such that all of the exponents of its factorial are odd. In other words, if $n\#$ denotes the product of all the primes less than or equal to $n$, is there an $n$ such that the number

$$\frac{n!}{n\#}$$ is a square?. Since I didn't know what to try I just wrote a very rough python code to check for numbers with that property, and after checking for $n\leq10^5$, the only values are $2,3,4,5$. I didn't want to check more because it took about $20$ minutes to run. I'm very new to programming so I don't doubt the code can be improved, feel free to let me know if you managed to check for bigger $n$. Are these the only ones? And how could I start proving it if so?

Any help is appreciated

My code:

from math import log
from time import time
def s(n,p):
   N=int(log(n,p))
   s=0
   for i in range(1,N+1):
       s=s+int(n/(p**i))
   return s
def P(n):
   prime=[True for i in range(n+1)]
   p=2
   while(p*p<=n):
       if(prime[p]==True):
           for i in range(p*p,n+1,p):
               prime[i]=False
       p=p+1
   l=[]
   for p in range(2,n+1):
       if(prime[p]):
           l.append(p)
   return l
n=int(input("Enter a number greater than or equal to 2: ",))
ti=time()
l=[]
for i in range(2,n+1):
   k=0
   for p in P(i):
       if(s(i,p)%2==1):
           k=k+1
   if(k==len(P(i))):
       l.append(i)
tf=time()
print("There are",len(l),"numbers n from 1 to",n,"such that n! has all of its exponents odd, and these are:")
for i in l:
   print(i)
print("This code took",round(tf-ti,2),"seconds to run")