[seqfan] Re: Add to an integer its distinct factors and loop

Jack Brennen jfb at brennen.net
Fri Jun 5 21:34:12 CEST 2009

I've turned a little PARI/GP program loose on the problem and it
seems very unlikely that the graph rooted at 48 is finite (under
the assumption that factorizations into more than two factors are

I base this on the number of nodes which I've already found in the
graph which contain thousands of successor nodes.  The first such
easily found node is at 2893800, which is reachable in 46 steps
from 48, and which has 3165 possible factorizations into distinct
factors.  Continuing a depth-first search, at 286 steps from 48,
we can reach the number 3715394712411723840, which has 20472 such

The breadth of the rooted tree at 48 seems to grow too fast to
ever die out.

franktaw at netscape.net wrote:
> Close, but it is not only factorizations into two factors that we are 
> considering.  So, if n = product_{i=1}^k a_i with a_i < a_{i+1} for 1 
> <= i < k and k > 1, there is an arrow from n to n + sum_{i=1}^k a_i.
> This more restrictive definition is of some interest, though.  To 
> extend Hagen's remarks, note that if n is even, everything pointed to 
> by n is divisible by a smaller power of two than n; so any path will 
> fairly quickly come to only odd numbers.  I think there still are 
> infinite paths, but it isn't as clear as for the original problem.
> Franklin T. Adams-Watters
> -----Original Message-----
> From: Hagen von EItzen <math at von-eitzen.de>
> Ah, now I see:
> We are considering the directed graph with the natural numbers as 
> vertices
> and an edge from n to m iff there are natural numbers a,b such that
> 1<a<b and n=a*b and m=n+a+b.
> The question then is: Are there infinite paths in this graph?
> (And related: How long is the longest path starting at n? Etc.)
> As already noted, primes and squares of primes are obvious end points.
> Other trivial observations:
> If n is not a multiple of 4, it points only to odd numbers;
> If n is a power of two, it points only to even numbers;
> all other numbers (i.e. multiple of 4 but not power of 2) point to
> numbers of both parities.
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list