# Is the set of all numbers which divide a specific function of their prime factors, infinite?

Consider a number $n$ with prime factorization $n=p_1^{k_1} \cdot p_2^{k_2} \dots \cdot p_z^{k_z}$. We define a function $f(n)$ to be $f(n)=(p_1^{k_1+1}-1) \cdot (p_2 ^{k_2 +1}-1) \dots \cdot (p_z^{k_z+1}-1)$. Let $S$ be the set that contains all odd integers $n > 2$ such that $n|f(n)$. What properties of $S$ can be deduced? More specifically:

Is $S$ finite or infinite? What are some numbers that can be part of $S$? Is there a general form to these numbers?

I really dont know where to start, at all. Thanks for the help!

-
The first member of $S$ seems to be $819 = (3^2)(7)(13)$, which has $f(819) = (256)(819)$. There are no others up to $10^6$. –  Robert Israel Jan 28 '12 at 0:24
Echoing Will Jagy's question: why? Is there some reason to be interested in this set? –  Gerry Myerson Jan 28 '12 at 5:16

The main thing is that the number $n$ cannot be squarefree, as it has a largest prime factor $r$ which is at least 2 larger than any other prime factor $p,$ so $r$ does not divide any $p_j^2 - 1 = (p_j + 1)(p_j -1).$

Anyway, I wrote out a little grid by hand, and I get another example with $$n = 3^4 \cdot 5 \cdot 7 \cdot 11^2 \cdot 19 = 6,517,665.$$ with $$f(n) = 2^{12} \cdot 3^4 \cdot 5^2 \cdot 7 \cdot 11^2 \cdot 19.$$

Note that your function is a little bit peculiar. Your $f(n) = \sigma(n) \cdot (p_1 - 1)(p_2 - 1)\cdots (p_z - 1),$ where $\sigma(n)$ is the sum of the divisors of $n.$ Where did you get this problem?

Another example with $$n = 3^4 \cdot 5^4 \cdot 11^3 \cdot 31 \cdot 61 \cdot 71 = 9,046,757,919,375.$$ with $$f(n) = 2^{20} \cdot 3^5 \cdot 5^4 \cdot 7 \cdot 11^3 \cdot 31 \cdot 61 \cdot 71.$$

EDIT, Saturday morning: as an "operations research" problem, this has a fairly clear approach in terms of a computer program. Not the same ordering Raymond used in his exhaustive search, yet exhaustive nevertheless. Fix one bound on primes used, call it $B,$ so all primes $p_j < B.$ Fix a second bound $M \geq B^2$ which bounds exponents as in $p^{k+1} < M.$ So, for each $p < B,$ the exponent bound $k_p$ will be $$k \; \leq \; \; k_p = -1 + \left\lfloor \frac{\log M}{\log p} \right\rfloor$$

Next, for each pair $(p,k)$ with $p < B$ and $p^{k+1} < M,$ perform a strictly limited small factoring of $p^{k+1} - 1,$ do trial division by only those primes $q$ that are also smaller than $B.$ The point here is that we do not care what prime factors there might be that are larger than $B,$ we would ignore them anyway. So the factoring step is lightning fast.

Suppose there are $b$ odd primes up to $B.$ So, for each pair $(p,k),$ save a list/vector, for each odd prime $q < B$ the entry is the exponent $v_q (p^{k+1} - 1).$

The search is now, for each odd $p < B,$ choose an exponent $0 \leq k \leq k_p,$ retrieve the list of all the $v_q,$ add on, resulting in a complete factorization of a candidate number $n$ and a factorization, of $f(n)$ using only primes $q < B.$ This is enough information to decide whether $n | f(n).$ I did something like this by hand, first with $B=20,$ later with $B=75.$ However, I was making selections by eye. There may be, as there usually are, ways to build in selection criteria to avoid checking all possible $b$-tuples. Looking at Raymond's list again, I would also suggest varying the bounds per prime, we might as well allow $3^k$ for pretty large $k,$ but beginning with $5$ we can be more strict with the bounds, so as to cut down on the final search space.

In case it is possible to have two solutions that are relatively prime, the product of two such is a new solution. So far, though, it appears that 3 is a factor of all solutions, which makes this comment likely superfluous.

-
Here's one that does not have $3$ as a factor: $$\left( 5 \right) ^{21} \left( 7 \right) ^{7} \left( 11 \right) ^{4} \left( 23 \right) ^{2} \left( 29 \right) \left( 41 \right) \left( 71 \right) \left( 79 \right) \left( 83 \right) \left( 89 \right) \left( 139 \right) \left( 167 \right) \left( 179 \right) \left( 521 \right) \left( 571 \right) \left( 601 \right) \left( 761 \right) \left( 1201 \right)$$ $$\left( 1523 \right) \left( 12207031 \right) \left( 9137 \right) \left( 3221 \right) \left( 5281 \right) .$$ –  Robert Israel Jan 29 '12 at 21:29
@RobertIsrael , that's great! –  Will Jagy Jan 29 '12 at 21:37
@Robert: Congratulations, that's impressive! Exhaustive search? :-) –  Raymond Manzoni Jan 29 '12 at 22:26
Not quite. It went something like this. Start with some positive integer $x_0$, say a power of $5$. If $f(x_0)$ is divisible by $p^k$ where $p$ is prime and $(x_0, p)=1$, then for $1 \le j \le k$ the denominator of $f(p^j x_0)/(p^j x_0)$ divides the denominator of $f(x_0)/x_0$. And hopefully its numerator will have some new prime factors... –  Robert Israel Jan 30 '12 at 1:48
@RobertIsrael So, exhausting but not exhaustive. –  Will Jagy Jan 30 '12 at 3:50

As a complement to Will Jagy's fine analysis I'll just add the result of an exhaustive search up to $4\cdot 10^9$ followed by a search restricted to odd numbers $n$ whose prime factors $p^k$ verify $p\le 73,\ p^k\le 11^3$ using Will Jagy's method :

$\begin{array} {rl|l} n & \text{factor(n)} & \text{factor(f(n))} \\ \hline \\ 1 & 1 & 1 \\ 819 & 3^2\cdot 7\cdot 13 & 2^8\cdot 3^2\cdot 7\cdot 13 \\ 2941029 & 3^5\cdot 7^2\cdot 13\cdot 19 & 2^{10}\cdot 3^5\cdot 5\cdot 7^2\cdot 13\cdot 19 \\ 6517665 & 3^4\cdot 5\cdot 7\cdot 11^2\cdot 19 & 2^{12}\cdot 3^4\cdot 5^2\cdot 7\cdot 11^2\cdot 19 \\ 14705145 & 3^5\cdot 5\cdot 7^2\cdot 13\cdot 19 & 2^{13}\cdot 3^6\cdot 5\cdot 7^2\cdot 13\cdot 19 \\ 1010238075 & 3^4\cdot 5^2\cdot 7\cdot 11^2\cdot 19\cdot 31 & 2^{17}\cdot 3^4\cdot 5^3\cdot 7\cdot 11^2\cdot 19\cdot 31 \\ 2279297475 & 3^5\cdot 5^2\cdot 7^2\cdot 13\cdot 19\cdot 31 & 2^{18}\cdot 3^6\cdot 5^2\cdot 7^2\cdot 13\cdot 19\cdot 31 \\ \hline \\ 528901498125 & 3^5\cdot 5^4\cdot 7^3\cdot 11\cdot 13\cdot 71 & 2^{20}\cdot 3^5\cdot 5^4\cdot 7^3\cdot 11\cdot 13\cdot 71 \\ 9046757919375 & 3^4\cdot 5^4\cdot 11^3\cdot 31\cdot 61\cdot 71 & 2^{20}\cdot 3^5\cdot 5^4\cdot 7\cdot 11^3\cdot 31\cdot 61\cdot 71 \\ 63327305435625 & 3^4\cdot 5^4\cdot 7\cdot 11^3\cdot 31\cdot 61\cdot 71 & 2^{24}\cdot 3^6\cdot 5^4\cdot 7\cdot 11^3\cdot 31\cdot 61\cdot 71 \\ \end{array}$

(people finding other solutions should feel free to edit this table!).

I must add Robert Israel's 'Far Away' solution (without $3$ factor) : $5^{21}\cdot 7^7\cdot 11^4\cdot 23^2\cdot 29\cdot 41\cdot 71\cdot 79\cdot 83\cdot 89\cdot 139\cdot 167\cdot 179\cdot 521\cdot 571\cdot 601\cdot 761\cdot 1201$ $\cdot 1523\cdot 12207031\cdot 9137\cdot 3221\cdot 5281$

Your sequence 819,2941029,... appears unknown to The On-Line Encyclopedia of Integer Sequences™. You could propose to add your sequence there (perhaps with some motivation that we too could appreciate :-)).

EDIT : I see no clear regularity in this sequence (except that only relatively small primes seem involved in $n$ and only very small ones in $\frac{f(n)}n$) and would conjecture that the sequence is infinite...

UPDATE: Since this problem was given at a calculator-free contest and to answer Sarah's questions let's try to find solutions without computer (using more or less Robert Israel's method). In fact finding solutions this way will be much faster and easier than using brute force.

The first thing to observe is that $f$ defines what is called a 'multiplicative function' in number theory : $$f(m\cdot n)=f(m)\cdot f(n)\ \ \text{for}\ \ (m,n)=1$$

This implies that we will only need to examine $f(p^k)$ for $p$ prime and $k\in \mathbb{N}$. To save some place I'll replace the $f$ function by the function $F$ obtained by removing the powers of $2$ and make a little table of $F(p^k)$ for small values of $p$ and $k$ (the first thing to do when you don't know what to do!) :

$\begin{array} {r|ccccc} p & k=1 & 2 & 3 & 4 & 5\\ \hline \\ 3 & 1 & 13 & 5 & 11^2 & 7\cdot 13 \\ 5 & 3 & 31 & 3\cdot 13 & 11\cdot 71 & 3^2\cdot 7\cdot 31 \\ 7 & 3 & 3^2\cdot 19 & 3\cdot 5^2\\ 11 & 3\cdot 5 \\ 13 & 3\cdot 7 \\ 17 & 3^2 \\ 19 & 3^2\cdot 5 \\ \end{array}$

$F(3^1)=\frac{3^2-1}8=1$ doesn't look interesting (we lost the initial $3$ and got nothing)
$F(3^2)=\frac{3^3-1}2=13$ seems more interesting so let's search (not at all inspired by the neatly ordered table above...)

• $F(13)=\frac{168}8=3\cdot 7$ (an additional $3$ and a new prime $7$) so let's search :
• $F(7)=3$ and we got our first solution :

$F(3^2\cdot 7\cdot 13)= 3^2\cdot 7 \cdot 13$

Let's try this again with the second interesting value of the table :
$F(3^3)=5$ so let's search $F(5)$ :

• $F(5)= 3 \cdots$ not enough $3$ to continue... Next try :

$F(3^4)=11^2$

• $F(11^2)=5\cdot 7\cdot 19\\$ we got $F(5)=F(7)=3$ so let's search
• $F(19)= 3^2\cdot 5$

and we found our second solution :

$F(3^4\cdot 5\cdot 7\cdot 11^2\cdot 19)=3^4\cdot 5\cdot 7\cdot 11^2\cdot 19$

I'll let you find other solutions too!

-
@Dear Will: your method is clearly much more efficient and I'll have to try it tomorrow morning. –  Raymond Manzoni Jan 29 '12 at 0:24
I note you do have some entries with $11^2,$ so it would be necessary to have $M \geq 1331$ to find these. I was mistaken about the 1024. –  Will Jagy Jan 29 '12 at 1:49
I think for the OEIS sequence you should remove the artificial restrictions that $n$ is odd and $> 2$. So the sequence will start $1, 6, 24, 28, 40, 84, 120, 234, 360, 496, 672, 819, 936$ –  Robert Israel Jan 29 '12 at 3:33
@Dear Will: I implemented your algorithm in pari/gp and got my table (in fact your full range $B=32$, $M=1331\$) in 7s (this could be further optimized...). But new solutions clearly require more primes and times (I got only $135,654,962,625\$ at this point...) and my scripts continue running... –  Raymond Manzoni Jan 29 '12 at 19:13
My only regret is that I cannot upvote the update, since I already upvoted the original. –  Gerry Myerson Feb 2 '12 at 22:32