10
$\begingroup$

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!

  • 3
    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$.2012-01-28
  • 6
    Echoing Will Jagy's question: why? Is there some reason to be interested in this set?2012-01-28

2 Answers 2

8

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.

  • 2
    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) .$$2012-01-29
  • 0
    @RobertIsrael , that's great!2012-01-29
  • 0
    @Robert: Congratulations, that's impressive! Exhaustive search? :-)2012-01-29
  • 0
    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...2012-01-30
  • 2
    @RobertIsrael So, exhausting but not exhaustive.2012-01-30
5

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!

  • 0
    @Dear Will: your method is clearly much more efficient and I'll have to try it tomorrow morning.2012-01-29
  • 0
    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.2012-01-29
  • 0
    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$2012-01-29
  • 0
    @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...2012-01-29
  • 0
    @Robert: you are right the odd constraint seems restrictive (and $1$ should be included). Anyway the odd terms seem interesting in their own way and pretty sparse... so that both sequences could be added! Cheers2012-01-29
  • 0
    @RaymondManzoni , glad it worked out. That is how I got my two solutions, inspecting what I had and seeing that I could throw in first powers of some larger primes (61, 71) by carefully adjusting the exponents on smaller primes. The biggest restriction seemed to be 5, a large exponent on 5, in $n,$ gives some opportunities, but then it is not so easy to arrange a high enough power of 5 in $f(n).$2012-01-29
  • 0
    @RaymondManzoni, so, my second solution would need $B=72, \; M=14641,$ again because of the exponent on $11.$ I do not have a clear idea of how much the program slows when increasing either bound. On the other hand, I once ran a program from 2004-2007. Restarts after it exhausted each file of raw data or after power outages.2012-01-29
  • 0
    @Will: much I fear... the time should be proportional to the product of the $\left(\rm round\left( \frac{\log M}{\log p_k} \right)+1\right)\ $ in my case. This mean $114\ $ hours for $B=74\ $ $M=1331\ $ if I can't speed up the internal loop...2012-01-29
  • 0
    @Raymond, five days is a bit long. For such jobs, I was able to run them on a separate machine under a nohup command (not sure if gp supports that). If it is on a computer you also need for other purposes, it is certainly not worth it. I'm wondering what Robert figured out that led him to his giant solution.2012-01-30
  • 0
    @Will: yes $48$ minutes is better! I got a further speedup of $8$ and replaced my upper bound for $k$ by $\left\lfloor \frac{\log M}{\log p}+\frac1{10} \right\rfloor\ $ (to avoid searching $p^2$ for large $p$). Out of curiosity what was your computer searching during the years $2004$-$2007$ ?2012-01-30
  • 0
    @RaymondManzoni , excellent work. Good algorithm adjusting... The three-year search was for spinor-regular integral positive ternary quadratic forms. See pages 11-12 in http://arxiv.org/abs/1010.3677. I can recommend Jones and Pall (1939) where the notion was discovered (but not so named), if you email me I can send you a pdf, also Chan and Earnest (2004). They made me revise a ton, the article that will actually appear does not include the spinor regular section and is about half length of the arXiv item.2012-01-30
  • 0
    @Will: Thanks! Interesting work with interesting people I must say (I like modular forms and Ramanujan's work!). It is always funny to discover all these links between such different subjects.2012-01-31
  • 0
    Raymond- what observations did you make to write the table? Did you use a program to brute force? What specifically about 819, say, makes it exactly fit the description? I speak of careful mathematical observation as opposed to computation- something that could be done without a calculator. I saw this on a calculator-free contest I did last week and hadn't an idea about how to do it. The odd constraint made it especially difficult, as guessing and checking is futile in this problem2012-02-02
  • 0
    @Sarah: I updated my answer. So it was a calculator-free constant. Could you provide us the text of the problem? Thanks,2012-02-02
  • 1
    My only regret is that I cannot upvote the update, since I already upvoted the original.2012-02-02
  • 0
    @Gerry: Thanks anyway for the attention Gerry! Cheers,2012-02-02
  • 0
    Can't find the commenting field, but here is the text of the problem from the contest. For a positive integer $n >1$ having a prime factorization $(p_1^{e_1}* p_2^{e_2}*p_3^{e_3}... *p_k^{e_k})$ define $f(n)= (p_1^{e_1+1}-1)(p_2^{e_2+1}-1)...(p_k^{e_k+1}-1)$. FInd an odd positive integer such that $n$ divides $f(n)$.2012-02-03
  • 0
    Only one solution was needed so no new information about what the 'challenger' knew for us... Nice problem anyway!2012-02-03