mersenneforum.org > Data Sum of bits of prime factors exceed exponent on M1999
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-12-29, 01:34 #1 alpertron     Aug 2002 Buenos Aires, Argentina 2×733 Posts Sum of bits of prime factors exceed exponent on M1999 The number M1999 is completely factored. In the page https://www.mersenne.ca/manyfactors....max=100.000000 the sum of bitsizes of the prime factors should equal the exponent 1999, but the number 2002.20 is shown. If we sum the bitsizes of the factors shown in https://www.mersenne.ca/exponent/1999, we get 1998.999 which is correct because of the small round-off, so the problem is in the previous Web page.
2021-12-29, 02:39   #2
Dr Sardonicus

Feb 2017
Nowhere

609410 Posts

Quote:
 Originally Posted by alpertron The number M1999 is completely factored. In the page https://www.mersenne.ca/manyfactors....max=100.000000 the sum of bitsizes of the prime factors should equal the exponent 1999, but the number 2002.20 is shown. If we sum the bitsizes of the factors shown in https://www.mersenne.ca/exponent/1999, we get 1998.999 which is correct because of the small round-off, so the problem is in the previous Web page.
I'm stumped on what they did to get that result.

Of course, the sum of the number of bits in the factors can exceed the number of bits in the product, but the number of bits in a positive integer is always a positive integer. The number of bits in the prime factors of M1999 add up to 2003.

They must have rounded 2003 down to 2002.2

 2021-12-29, 09:26 #3 ATH Einyen     Dec 2003 Denmark 1101010101102 Posts https://www.mersenne.ca/exponent/1999 20.785 + 69.097 + 85.709 + 112.042 + 130.432 + 162.350 + 1,418.584 = 1,998.999 These are ok, the bits sum to 1998.999, but on the other page the bitsize of the P428 (Largest factor (bits)) is wrong: 1,421.79 instead of 1,418.584: https://www.mersenne.ca/manyfactors....max=100.000000 Last fiddled with by ATH on 2021-12-29 at 09:30
 2021-12-29, 10:08 #4 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2·32·89 Posts An obvious easy/fast way to get a very good approx for the fractional bits: for x=a*2^e, where 02^63) it is just e+log2(a), what you could get in O(1) time in gmp (from (a,e)).
2021-12-29, 11:06   #5
alpertron

Aug 2002
Buenos Aires, Argentina

2×733 Posts

Quote:
 Originally Posted by Dr Sardonicus I'm stumped on what they did to get that result. Of course, the sum of the number of bits in the factors can exceed the number of bits in the product, but the number of bits in a positive integer is always a positive integer. The number of bits in the prime factors of M1999 add up to 2003. They must have rounded 2003 down to 2002.2
The "number of bits" or "bitsize" in this context is the logarithm to the base 2 of the number without rounding up to the next integer. That's why the sum should be 1999.

2021-12-29, 14:18   #6
Dr Sardonicus

Feb 2017
Nowhere

2·11·277 Posts

Quote:
 Originally Posted by alpertron The "number of bits" or "bitsize" in this context is the logarithm to the base 2 of the number without rounding up to the next integer. That's why the sum should be 1999.
Yes, I know that. And that's what made it hard for me to understand the error. It's way too big to attribute to rounding. It's almost as big as the sum (2003) of the number of bits of the factors.

The fact that the error made it into the outside world tells me that there was no "sanity check" that the sum of the logs of the factors has to be equal to the log of the product.

Now it seems the problem was that the value used for the base-2 log of the largest factor was too high by 3.2 or so. I still don't know how that could have happened.

2021-12-29, 14:57   #7
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

7,103 Posts

Quote:
 Originally Posted by Dr Sardonicus Now it seems the problem was that the value used for the base-2 log of the largest factor was too high by 3.2 or so. I still don't know how that could have happened.
It looks to me close to a transcription error of some sort. Log2(10)=3.32. Accidental insertion of an extra digit that's low value before taking the log2 would do it. For examplee, (log(1123456789)-log (123456789))/log2(10) ~3.186.
Or perhaps a digit-computing fallacy. 1.3E10 has 11 decimal digits as a base 10 integer, but log10(1.3E10) is 10.114 not 11 or 11.114. Either way, looks like there was a human in the chain of custody.

Last fiddled with by kriesel on 2021-12-29 at 15:00

2021-12-29, 15:11   #8
Dr Sardonicus

Feb 2017
Nowhere

137168 Posts

Quote:
 Originally Posted by kriesel It looks to me close to a transcription error of some sort.
I tried to reproduce the error by adding an extra digit, or mistyping one of the leading digits, without success.

Perhaps they simply input the wrong number entirely for the last bitsize calculation. That would qualify as a transcription error.

Quote:
 Either way, looks like there was a human in the chain of custody.
I agree, absolutely.

 2021-12-29, 15:21 #9 charybdis     Apr 2020 15538 Posts The incorrect figure of 1421.79 bits almost certainly comes from taking the number of digits in the factor, 428, and multiplying it by log2(10). The same can be seen with M1723 for example.
2021-12-29, 16:41   #10
Dr Sardonicus

Feb 2017
Nowhere

2·11·277 Posts

Quote:
 Originally Posted by charybdis The incorrect figure of 1421.79 bits almost certainly comes from taking the number of digits in the factor, 428, and multiplying it by log2(10). The same can be seen with M1723 for example.
Boom!

So the error is using number of decimal digits instead of base ten log (apparently only on the largest factor) before converting to base two log.

The error incurred thereby in the base two log of N is (1 - frac(log(N)/log(10)))*log(10)/log(2). If the lead digit of N is 1 (as with the largest prime factor of M1999, the fractional part will be small, and the error will be close to 3.321.

 2021-12-29, 17:14 #11 axn     Jun 2003 34×67 Posts Unless the complaints go in the main mersenne.ca thread (sticky), James H may not see this.

 Similar Threads Thread Thread Starter Forum Replies Last Post shubhra Information & Answers 6 2022-01-03 22:17 Raydex Information & Answers 11 2021-02-20 23:51 carpetpool carpetpool 0 2020-03-12 02:50 eight6225219 Miscellaneous Math 7 2019-11-21 14:59 ewmayer Lounge 4 2006-09-06 20:57

All times are UTC. The time now is 23:46.

Wed Nov 30 23:46:30 UTC 2022 up 104 days, 21:15, 0 users, load averages: 1.06, 1.00, 1.01

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.

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