 mersenneforum.org #of divisors Series
 Register FAQ Search Today's Posts Mark Forums Read  2022-06-10, 19:48 #1 oreotheory   "NT" May 2022 U.S. 19 Posts #of divisors Series I've been playing around with the following (potentially interesting) series: You take a number (let's take 32 for example) and find how many divisors it has (32 has 6 divisors). If the number of divisors divides that number perfectly (without remainder), then you divide (32/6). If it doesn't divide without remainder (like 32 doesn't), you multiply by the number of divisors instead, so 32*6=192. And you continue this process until you get to 1 or a repeating series. So for 32, the series is 32, 192, 2688, 84, (7, 14, 56)... The part in parentheses is an infinite loop. Most numbers I've tried (which is only very low numbers) seem to go down to a prime loop (like 32 goes to 7). Some non-prime numbers form a small 3-number loop with themselves (as all the primes do). 25 and 49 behave this way (but not 81 which goes down to a 5 loop). 55 is the first number to enter a loop of a number greater than itself (3696 loop). 65 is the next number (entering a 4368 loop). Does anyone have any insight into this series? How will larger numbers behave? Will there be lots of numbers like 55 which enter orbit with some large number? Would anyone be interested in visualizing this series, creating some kind of tree or graph? Have fun and thanks in advance...   2022-06-10, 23:56 #2 Viliam Furik   "Viliam Furík" Jul 2018 Martin, Slovakia 13×59 Posts For a moment I thought about using only the proper divisors, but this lead me very quickly to a realization of a problem with primes, which would then have only 1 divisor. These number series are a really nice topic to explore. Using gcd it might get more interesting, e.g. multiply the number and its divisor count and then divide by their gcd^2 ( n -> n * dc(N) / gcd(n, dc(n)) ^ 2 ) - this way the number can get smaller if the gcd is greater than 1, and will get bigger if it's 1. It's basically a smoother version of your multiply/divide approach, as it does both complete multiplication (when gcd is 1) and complete division (when gcd is the divisor count), but also an "incomplete" multiplication, i.e. the result is less than the number times the divisor count. 1 -> 1 2 -> 1 3 -> 6 -> 6 4 -> 12 -> 2 -> 1 5 -> 10 -> 10 6 -> 6 7 -> 14 -> 14 8 -> 2 -> 1 9 -> 18 -> 3 -> 6 -> 6 10 -> 10 11 -> 22 -> 22 12 -> 2 -> 1 13 -> 26 -> 26 14 -> 14 15 -> 60 -> 5 -> 10 -> 10 16 -> 80 -> 8 -> 2 -> 1 17 -> 34 -> 34 18 -> 3 -> 6 -> 6 19 -> 38 -> 38 20 -> 30 -> 60 -> 5 -> 10 -> 10 Based on these it seems it only stops on 2*p (for primes p other than 2) and 1. It also seems it might be easy to prove this based on the prime factorization. But I am too lazy to do that now, and a counterexample would be cool! P.S. In case it's not easy to prove this behavior, I hereby coin the name (your, oreotheory's, surname)-Furík conjecture. Last fiddled with by Viliam Furik on 2022-06-11 at 00:02   2022-06-11, 00:28 #3 Viliam Furik   "Viliam Furík" Jul 2018 Martin, Slovakia 2FF16 Posts Okay, I have found something: 25 -> 75 -> 50 -> 75 (5^2 -> 3*5^2 -> 2*5^2 -> 3*5^2)   2022-06-11, 06:34 #4 bur   Aug 2020 79*6581e-4;3*2539e-3 7×83 Posts I wrote a simple PARI script that prints the series. First parameter is the number you want to test, the second parameter is optional and sets the number of elements that are calculated. Since there is no loop detection you need to use that second parameter to break any occuring loops manually... Code: tau(n) = { t = 1; f = factor(n); for(i = 1, matsize(f), t *= f[i,2]+1 ); return(t); } series(n,j) = { i = 0; until(i == j, t = tau(n); if(Mod(n,t) == 0, print(n /= t), print(n *= t) ); i++; ) }   2022-06-11, 20:33 #5 henryzz Just call me Henry   "David" Sep 2007 Liverpool (GMT/BST) 23·7·107 Posts Many cases seem to provably terminate. Many cycles are also provable. There is a fairly obvious cycle that occurs for all primes > 2. (p -> 2*p -> 8*p -> p) @Villiam 75 goes to 450 not 50. There is a cycle for p^2 with p > 3. (p^2 -> 3*p^2 -> 18*p^2 -> p^2) 3*p -> 12*p -> p -> see above cycle For p>3: 3^3*p -> 2^3*3^3*p -> 2^8*3^3*p -> 2^5*3*p -> 2^2*p=4*p -> 4*p -> 6*4*p=24*p -> 16*24*p=384*p -> 384/32*p -> 12*p -> p -> see above cycle For for p and q not equal to 2 or 5: 5*q^3*p -> 80*q^3*p -> q^3*p For p and q > 5: p*q -> 2^2*p*q -> 2^4*3*p*q -> 2^7*3*5*p*q -> 3*5*p*q -> 2^4*3*5*p*q -> 3*p*q -> 2^3*3*p*q -> 2^8*3*p*q -> 2^11*3^3*p*q -> 2^5*3^2*p*q -> 2^2*p*q -> cycle p*q*r seems to grow to very large numbers.   2022-06-11, 22:59   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

232558 Posts Quote:
 Originally Posted by bur Code: tau(n) = { t = 1; f = factor(n); for(i = 1, matsize(f), t *= f[i,2]+1 ); return(t); }
replace tau(n) with #divisors(n)   2022-06-12, 00:58   #7
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

13×59 Posts Quote:
 Originally Posted by henryzz @Villiam 75 goes to 450 not 50.
Let me correct you.

Quote:
 Originally Posted by Viliam Furik These number series are a really nice topic to explore. Using gcd it might get more interesting, e.g. multiply the number and its divisor count and then divide by their gcd^2 ( n -> n * dc(N) / gcd(n, dc(n)) ^ 2 ) - this way the number can get smaller if the gcd is greater than 1, and will get bigger if it's 1.
I was explaining my improved version of the original rule for the sequence. Thus 75 goes to 50. At least in my version, that is.

75 = 3 * 5^2, that is 6 divisors, 6 = 2 * 3, gcd(75, 6) = 3, thus 75 / 3 * 6 / 3 = 25 * 2 = 50

Relaxing the divisibility condition makes it much more elegant in its behavior.   2022-06-12, 10:44   #8
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

23×7×107 Posts Quote:
 Originally Posted by Viliam Furik Let me correct you. I was explaining my improved version of the original rule for the sequence. Thus 75 goes to 50. At least in my version, that is. 75 = 3 * 5^2, that is 6 divisors, 6 = 2 * 3, gcd(75, 6) = 3, thus 75 / 3 * 6 / 3 = 25 * 2 = 50 Relaxing the divisibility condition makes it much more elegant in its behavior.

I misread your posts and thought that example was on the original definition.
3^2*p^2*q^2*r^2
3^2*p^2*q^8
3^2*p^26
All terminate with a length 1 cycle. The trick is having the square root of number of divisors be the result of the gcd. I believe there would be examples with all primes 5^4 etc. There may be more complex examples.
This definition does looks like it avoids the continuously rising powers of small primes that happens with the first definition.

Last fiddled with by henryzz on 2022-06-12 at 10:44   2022-06-12, 10:52   #9
Viliam Furik

"Viliam Furík"
Jul 2018
Martin, Slovakia

13×59 Posts Quote:
 Originally Posted by henryzz The trick is having the square root of number of divisors be the result of the gcd.
Ooooh, smart. So there are infinitely many 1-cycles with these known formats.   2022-06-12, 16:53 #10 Stargate38   "Daniel Jackson" May 2011 14285714285714285714 22·3·59 Posts @bur: I started with 10^32-1, and the sequence seems to be open-ended. After 160 terms, I get this number: http://www.factordb.com/index.php?id...00003600111633   2022-06-12, 22:58   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

112×13 Posts Quote:
 Originally Posted by Stargate38 @bur: I started with 10^32-1, and the sequence seems to be open-ended. After 160 terms, I get this number: http://www.factordb.com/index.php?id...00003600111633
Interesting, still yesterday thought that every number goes to cycle.

Looks like 578 is the first number that goes to infinity!
After 2000 iterations the factorization begins with: [2, 123877; 3, 28032; 5, 6837; 7, 2797;
The problem is that when the exponent of 2 is t in the factorization of N, then (t+1) divides numdiv(N), and if t+1 has a "large" r prime factor then likely N is not divisible by r, and you need to mulitple N by numdiv(N).
OK, this brings r as a factor to N, but then it will be even harder to clear also that r from N.
In this 2000 iterations range there are some iterations that the operation is division, so N->N/numdiv(N) and not multiplication. Though it is rare. [in almost all cases you need to check only the exponent of two to see if it was a division or multiplication].   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 0 2021-06-16 07:09 MattcAnderson MattcAnderson 1 2021-06-15 17:36 MattcAnderson MattcAnderson 3 2021-06-14 16:24 firejuggler Prime Sierpinski Project 2 2012-01-10 17:14 Citrix Math 10 2006-02-08 04:09

All times are UTC. The time now is 04:14.

Sat Aug 13 04:14:43 UTC 2022 up 36 days, 23:02, 2 users, load averages: 1.18, 1.30, 1.30