mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-06-10, 19:48   #1
oreotheory
 
oreotheory's Avatar
 
"NT"
May 2022
U.S.

19 Posts
Default #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...
oreotheory is offline   Reply With Quote
Old 2022-06-10, 23:56   #2
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

19·41 Posts
Default

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
Viliam Furik is offline   Reply With Quote
Old 2022-06-11, 00:28   #3
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

19·41 Posts
Default

Okay, I have found something:

25 -> 75 -> 50 -> 75 (5^2 -> 3*5^2 -> 2*5^2 -> 3*5^2)
Viliam Furik is offline   Reply With Quote
Old 2022-06-11, 06:34   #4
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default

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)[1],
  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++;
 ) 
}
bur is offline   Reply With Quote
Old 2022-06-11, 20:33   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

22×1,499 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2022-06-11, 22:59   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·3,313 Posts
Default

Quote:
Originally Posted by bur View Post
Code:
tau(n) = {
 t = 1;
 f = factor(n);
 for(i = 1, matsize(f)[1],
  t *= f[i,2]+1
 );
 return(t);
}
replace tau(n) with #divisors(n)
Batalov is offline   Reply With Quote
Old 2022-06-12, 00:58   #7
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

77910 Posts
Default

Quote:
Originally Posted by henryzz View Post
@Villiam 75 goes to 450 not 50.
Let me correct you.

Quote:
Originally Posted by Viliam Furik View Post
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.
Viliam Furik is offline   Reply With Quote
Old 2022-06-12, 10:44   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

22×1,499 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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.
Based on your revised 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
henryzz is offline   Reply With Quote
Old 2022-06-12, 10:52   #9
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

19×41 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Viliam Furik is offline   Reply With Quote
Old 2022-06-12, 16:53   #10
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

727 Posts
Default

@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
Stargate38 is offline   Reply With Quote
Old 2022-06-12, 22:58   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32×52×7 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
@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].
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
divisors summary MattcAnderson MattcAnderson 0 2021-06-16 07:09
discrete divisors MattcAnderson MattcAnderson 1 2021-06-15 17:36
prime divisors MattcAnderson MattcAnderson 3 2021-06-14 16:24
Looking for fermat divisors, n=90-120 firejuggler Prime Sierpinski Project 2 2012-01-10 17:14
Number of divisors of n? Citrix Math 10 2006-02-08 04:09

All times are UTC. The time now is 08:56.


Wed Sep 28 08:56:23 UTC 2022 up 41 days, 6:24, 0 users, load averages: 1.32, 1.24, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔