Factorial puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Factorial puzzle

Postby Goahead52 » Tue Aug 16, 2016 7:04 pm UTC

k!=m*phi(m)*n*phi(n)
k,m,n positive integers
phi is the Euler totient

Find the triplets (k,m,n) such as the equation above holds.

Examples :
k=7

m=5
n=21
or
m=7
n=15

(7,5,21) and (7,7,15) are solutions
k=8
(8,20,21) is solution

Do all the factorials have at least one solution?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorial puzzle

Postby Goahead52 » Wed Aug 17, 2016 1:15 pm UTC

Here is my theorem :
Let us call a number of form n*phi(n) an eulerian factorial number EFN (n positive integer > 0).
If mu(EFN)=-1 then n is prime (mu() is the Mobius function)

n=7
phi(7)=6
EFN(7)=7*6=42
mu(42)=-1 imply that 7 is prime

n=11
EFN(11)=110
mu(110)=-1 imply that 11 is prime

The converse is not true even if n is an EFN prime mu(n) could be equal to 0 or 1

Examples :
n=13
EFN(13)=156
mu(156)=0
n=43
EFN(43)=1806
mu(1806)=1

I`m really sorry to put my discovery here in the factorial puzzle.

Anyone for checking my claims to confirm or to infirm is welcome.
Any proof because I still do not understand why?
Is the theorem new? I do not know

Cauchy
Posts: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Factorial puzzle

Postby Cauchy » Fri Aug 19, 2016 2:00 am UTC

What is the point of having m and n? The Euler totient function is multiplicative, so unless you plan to have solutions with m and n sharing a factor, we can just talk about mn*phi(mn). Really, though, we should be splitting m and n up across their prime factors. So we have m = p_1^{m_1}p_2^{m_2}...p_a^{m_a} and n = q_1^{n_1}q_2^{n_2}...q_b^{n_b}, where each m_i and n_i is positive. Then, phi(m) = p_1^{m_1-1}(p_1-1)p_2^{m_2-1}(p_2-1)... and similarly for phi(n). We can really just talk about p_1^{d_1}*phi(p_1^{d_1})*p_2^d_2*phi(p_2^d_2)*..., where a given prime is allowed to appear up to two times.

It seems to me that if anything should work, a greedy algorithm would work. Let k! be 2^{k_1}3^{k_2}...p_c^{k_c}, where the primes are sorted in ascending order. The largest prime appearing in k! is p_c, with k_c = 1. So we put p_c^1 in our group of primes, and get p_c*(p_c-1) in our product. We divide k! by p_c(p_c-1) and continue (or else it doesn't divide evenly, in which case we couldn't possibly have a solution). When k_c is odd, we put p_c^{(k_c+1)/2} in our collection of primes, and when k_c is even, we put both p_c^{k_c/2} and p_c in our collection of primes (or any other choice of two whose exponents sum to (k_c/2 + 1); they all have the same total product). (When k_c is odd, we can only have p_c show up once, and when k_c is even, p_c must show up twice.) If we pick so as to satisfy the largest prime left unaccounted for at every step, I think our hand is forced at every step, so we come up with a unique answer, up to the small choices I noted you could make when k_c was even.

For k = 9, for instance, 9! = 2^7*3^4*5*7. We put 7^1 in our pool of primes, and divide by 7*(7-1) to get 2^6*3^3*5. We next put 5 into our pool, and divide by 5*(5-1) to get 2^4*3^3. We next put 3^2 in, and divide by 3^2*(3*(3-1)) to get 2^3. Finally, we put 2^2 in, and divide by 2^2*(2*(2-1)) to get 1, as desired. Our list of primes is 2^2, 3^2, 5, and 7, so as long as m and n are coprime and multiply to 2^2*3^2*5*7=1260, we get a solution, since 1260*phi(126) = 9!.

Your theorem is not very interesting, because mu(EFN(n)) = 0 except sometimes when n is prime. EFN is multiplicative and even except when n = 1, so if n has two different prime powers, EFN has a factor of 2^2 and hence mu(EFN) = 0.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorial puzzle

Postby Goahead52 » Fri Aug 19, 2016 3:05 pm UTC

I know that phi is multiplicative.
I was working on Eulerian Factorial Numbers (EFN) to represent any factorial as product of 2 EFN.
The EFN are new kind of numbers with many properties.
An EFN is of the form n*phi(n) where phi is the Euler totient.
If you mutiply 2 EFN you will obtain an other EFN.
etc....
I do not have enough energy to focus on.
You could improve your algorithm to find quickly a factorial product of 2 EFN.
There are many rules (or theorem) you could deduce to make an efficient algorithm if you study deeply the EFN.
Any theorem could very useful sometimes crucial depending on what we intent to solve.
Your comment about my new theorem is not right because you do not know where I was heading to.
Conclusion : any theorem is interesting (either theoretical or practical interest)
Anyway thank you for your comment and good luck

Demki
Posts: 192
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: Factorial puzzle

Postby Demki » Sun Aug 21, 2016 12:29 pm UTC

Here are your EFN on OEIS: https://oeis.org/A002618
Also n phi(n)=phi(n^(2))

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Factorial puzzle

Postby Goahead52 » Mon Aug 22, 2016 12:06 pm UTC

Thank you for pointing out to something even before creating the EFN.
Anyway any factorial could written in many ways as product of 2 EFN.
Building a quick algorithm to represent k!=F(n,m) where F(n,m) is a function depending on 2 variables is not hard. But finding links between n and m is too hard. The more k! become bigger the more the number of solutions explode. It become very hard to find some standardization for any factorial. With the input "k" you give automatically the values n and m.
No need to compute each time.
I`m talking about of k exceeding some size.

Cauchy
Posts: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Factorial puzzle

Postby Cauchy » Mon Aug 22, 2016 2:22 pm UTC

The link between m and n is that their product seems to be constant for a given k. I would be fairly surprised if there were solutions not generated by the algorithm I described.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests