A Jordan-Polya number is a number that can be factorized with factorials (i.e., $240=2!\cdot5!$) and I'm searching for an algorithm to test the property of being a Jordan-Polya number.
Obviously, the factorial of the largest prime factor $p$ of $n$ must divide $n$ if $n$ is a JP-number. Therefore, the existence of a number $m$ such that $p\le m<p'$ where $n/m!$ is JP and $p'$ is the successor prime of $p$, should be a necessary and sufficient condition.
I've tried to use this to construct the divide-and-conquer algorithm below, but for some reason, it doesn't work.
1. Function IsJp(input numb) boolean
2. if IsFactorial(numb) then return true
3. prime ← LargestPrimeFactor(numb)
4. for i = prime to NextPrime(prime) - 1
5. if (numb mod i!) = 0 then return IsJp(numb / i!)
6. next i
7. return false
When running in Forth there is trouble with a return stack overflow. So what is wrong? How can I correct the algorithm?
Edit: I think I found the problem: there should be a terminal case for failure in the beginning of the algorithm:
1. Function IsJp(input numb) boolean
2. if IsFactorial(numb) then return true
3. if IsPrime(numb) then return false
4. prime ← LargestPrimeFactor(numb)
5. for i = prime to NextPrime(prime) - 1
6. if (numb mod i!) = 0 then return IsJp(numb / i!)
7. next i
8. return false
Edit:
1. Function IsJp(input numb) boolean
2. if IsFactorial(numb) then return true
3. if IsPrime(numb) then return false
4. prime ← LargestPrimeFactor(numb)
5. for i = NextPrime(prime) - 1 to prime step -1
6. if (numb mod i!) = 0 then
7. if IsJp(numb / i!) then return true
8. next i
9. return false
This algorithm is tested with all 64-bit numbers in the table of the first 10,000 jp-numbers on OEIS.
Edit:
1. Function IsJp(input numb) boolean
2. if IsFactorial(numb) then return true
3. prime ← LargestPrimeFactor(numb)
4. for i = NextPrime(prime) - 1 to prime step -1
5. if (numb mod i!) = 0 then
6. if IsJp(numb / i!) then return true
7. next i
8. return false
A row was deleted, since not needed.