mersenneforum.org > Math Estimating the number of prime factors a number has
 Register FAQ Search Today's Posts Mark Forums Read

 2012-05-15, 18:28 #1 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 37×163 Posts Estimating the number of prime factors a number has Has anyone found a formula that gives the probability of a number with a given size having n prime factors? I haven't ever seen one and a google search didn't turn anything up.
 2012-05-15, 19:17 #2 mart_r     Dec 2008 you know...around... 23×37 Posts Maybe this post is relevant to your question: http://www.mersenneforum.org/showthread.php?t=13737 Last fiddled with by mart_r on 2012-05-15 at 19:21
2012-05-15, 22:00   #3
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by henryzz Has anyone found a formula that gives the probability of a number with a given size having n prime factors? I haven't ever seen one and a google search didn't turn anything up.
The Erdős-Kac theorem with continuity correction gives a decent estimate, but it's not very useful unless n is large.

 2012-05-16, 10:06 #4 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 603110 Posts My aim with this information is to estimate how likely it is for an aliquot sequence with for example 2^4*3*c100 to lose/keep the 3 on the next iteration. $\pi_k(n)=\frac{n(\log\log n)^{k-1}}{(k-1)!\log n}$ should be good enough especially if I can estimate the error. Since I am using this for aliquot sequences I know certain factors do not divide the composite. In the case of 2^4*3*c100 this is 2 and 3(Note I could also do with doing things like 2^4*7 not just the first n primes. The exponent 4 isn't crucial as well.)
 2012-05-20, 21:38 #5 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 178F16 Posts Is there a way of removeing a factor from this formula? For example if I know that 2 is not a factor of the composite. How much difference should this make? I imagine with 2 it would make quite a bit of difference. With much larger numbers e. g. 31 it wouldn't make nearly so much difference.
 2012-05-22, 04:22 #6 CRGreathouse     Aug 2006 5,987 Posts Use a weighted sum of the appropriate pi_k. For example, if you wanted the number of odd 3-almost-primes up to x, that's pi_3(x) - pi_2(x/2).
2012-05-22, 09:16   #7
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

136178 Posts

Quote:
 Originally Posted by CRGreathouse Use a weighted sum of the appropriate pi_k. For example, if you wanted the number of odd 3-almost-primes up to x, that's pi_3(x) - pi_2(x/2).
Brilliant thanks. Wierdly I actually thought of something similar while going to sleep last night.
Does this sort of start a chain where pi_2(x/2) needs correcting by subtracting from it pi_1(x/4) etc.?
This would lead to pi_k(x)-pi_(k-1)(x/2)+pi_(k-2)(x/4)-pi_(k-3)(x/8) ... which you would continue until you have the necessary precision.

2012-05-23, 01:13   #8
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by henryzz Brilliant thanks. Wierdly I actually thought of something similar while going to sleep last night. Does this sort of start a chain where pi_2(x/2) needs correcting by subtracting from it pi_1(x/4) etc.? This would lead to pi_k(x)-pi_(k-1)(x/2)+pi_(k-2)(x/4)-pi_(k-3)(x/8) ... which you would continue until you have the necessary precision.
No, one subtraction is good enough for that problem. But for more complicated problems you might need a lot of terms, yes.

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 Factoring 31 2018-01-29 10:41 noodles YAFU 2 2017-05-12 14:00 CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 kurtulmehtap Math 12 2010-05-03 14:02

All times are UTC. The time now is 20:28.

Thu Feb 2 20:28:42 UTC 2023 up 168 days, 17:57, 1 user, load averages: 1.27, 1.14, 1.11

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.

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