factorialprime factorizationprime numbers
I need to write a program to input a number and output it's factorial in the form:
$4!=(2^3)(3^1)$
$5!=(2^3)(3^1)(5^1)$
I'm now having trouble trying to figure out how could I take a number and get the factorial in this format without actually calculating the factorial.
Say given
5
need to get result of
$(2^3)(3^1)(5^1)$
without actually calculating
5!=120.
A related conjecture is posted at this link-that with the floor function you can get all naturals. I remember seeing a proof to that version with $\pi$ instead of $3$ a while ago, but can't find it now.
Not an answer but a comment on the problem:
I think the enumeration of such rearranged sequences is a graph theory question. Consider the undirected graph $G_n$ whose nodes are the numbers from $1$ to $n$. Draw an edge between $a$ and $b$ if $a+b$ is prime. Then by Bertrand's postulate you get a connected graph.
Arrangements of the numbers such that the sum of any two consecutive numbers is prime correspond to Hamiltonian paths of $G_n$. An example for $n=8$:
Note that the graph is bipartite. This gives you methods to find prime arrangements in $O(1.5^n)$ rather than $O(n!)$ as required for the brute force approach.
However I doubt that it really helps to prove for which numbers such an arrangement exists.
Best Answer
If $p$ is a prime, then the highest power $p^k$ of $p$ that divides $n!$ is given by $$k=\left\lfloor\frac{n}{p}\right\rfloor+ \left\lfloor\frac{n}{p^2}\right\rfloor+ \left\lfloor\frac{n}{p^3}\right\rfloor+ \cdots.\tag{1}$$
Here $\lfloor x\rfloor$ is the floor function, defined by $\lfloor x\rfloor$ is the greatest integer $\le x$.
Note that the sum in (1) is a effectively a finite (and usually short) sum: If $p^a\gt n$ then $\lfloor n/p^a\rfloor=0$.