mersenneforum.org Factorize a 129-digit number
 Register FAQ Search Today's Posts Mark Forums Read

2021-04-10, 02:02   #12
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts

Quote:
 Originally Posted by charybdis Wrong. The factors of OP's number are Code: 166447885293942400205064657834447096885456111524808377 1005632514199652040245190989819182186076324308468303514078693528739687994577 (I didn't find these myself, someone put them in factordb.) Both factors are 1 mod 8.
Thank you for the correcting my mistake charybdis.

Somehow I erred at computing the valuation(OP-Number-1,2) as 2 rather than 3.
In the integer field if valuation(n-1,2) =n' for any positive odd integer then if
m==a*b
if a'==m' then b'>a'
if a'<m' then b'==a'
Here my error was that m'==2 rather than 3 and since neither a' nor b' could be less than 2 then I wrongly concluded that one had to be equal to 2.

Again, thank you very much for the correction. Much appreciated.

Last fiddled with by a1call on 2021-04-10 at 02:15

2021-04-10, 02:57   #13
mersenneNoob

"Nigel"
Apr 2021

2·7 Posts

Quote:
 Originally Posted by CRGreathouse Let s = 33765749444723236975938383549571694531728722961303548619829414070181324100 so your number is s^2 + 1. Is there some special significance to s or s^2 + 1?
Yes there is. If you go to oeis A000522 then 2*a(32)*a(33)=s.

2021-04-10, 12:47   #14
Dr Sardonicus

Feb 2017
Nowhere

23·34·7 Posts

Quote:
 Originally Posted by a1call ETA III You can also be sure that at least one of the prime factors of OP-Number will be of the form 4*n+1 where n is an odd integer.
Since OP number divides s^2 + 1 for s given by frmky, all factors are congruent to 1 (mod 4), hence congruent to 1 or 5 (mod 8). OP number is congruent to 1 (mod 8). Hence, evenly many of its factors are congruent to 5 (mod 8).

And by golly, zero is even!

 2021-04-11, 10:51 #15 mersenneNoob   "Nigel" Apr 2021 2·7 Posts OP=?? Why did you all start calling the number OP-number?
2021-04-11, 10:54   #16
slandrum

Jan 2021
California

22·17 Posts

Quote:
 Originally Posted by mersenneNoob Why did you all start calling the number OP-number?
OP is Original Poster, the person who started the thread - in other words you.

2021-04-11, 15:59   #17
Dr Sardonicus

Feb 2017
Nowhere

11B816 Posts

Quote:
 Originally Posted by a1call Somehow I erred at computing the valuation(OP-Number-1,2) as 2 rather than 3.
There's a trick to find the remainder mod 8 that's so foolproof, it even works for me: just take the remainder mod 8 of the last 3 digits. In this case, the OP's number ends in 529, and 529 = 8*66 + 1.

Exercise: To compute the remainder of n (mod 2^k) or (mod 5^k), it suffices to compute the remainder of the last k decimal digits of n (mod 2^k) or (mod 5^k).

 2021-04-11, 16:43 #18 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,009 Posts I'm afraid you are giving me too much credit for being able to do arithmetic in my head. I actually used Pari and specifically remember getting 2 as the valuation. I can only assume that it must have been a typo somewhere. But thanks for the calculation trick. ETA Being a CAD designer for most of your life, pretty much strips you of being able to do any arithmetic in your head. It's sort of a "if you don't use, you lose it" in the extreme. Accordingly with the advent voice-recognition and speech-to-text software, I expect the future generations not being able to correctly spell a word if their lives depended on it. That would put me as much at home as it would kriesel out. Last fiddled with by a1call on 2021-04-11 at 17:01
 2021-04-11, 17:24 #19 LaurV Romulan Interpreter     Jun 2011 Thailand 100100111001012 Posts Yo don't need to do advanced math in your head, what he is referring to is the school-grade rules of divisibility, like "a number is divisible by 3 if the sum of digits is divisible by 3", "a number is divisible by 4 if the last two digits are divisible by 4", "a number is divisible by 5 if the last digit is 0 or 5", etc. For 4, any number can be written 100*x+y, where y<100, and 100*x is always divisible by 4, therefore for the number to be divisible by 4, is enough that y is divisible by 4. Ex: 1234 is not divisible by 4, because 34 is not divisible by 4, this number is 2 (mod 4). This works because you can write 1234 as 1200+34, and 1200 is always divisible by 4 (as is multiple of 100, so it is 4 times multiple of 25), so it is enough to examine the last 2 digits. You can apply that for 8, etc. Edit: For 8 there is even a simpler rule, where you look first if the third digit from the right (the "hundreds", i.e. the 2 in 1234) is odd or even, and according with it, you examine the last two. Can you say why that works, and how do we know at a simple glance that 1234 is 2 (mod 8)? Last fiddled with by LaurV on 2021-04-11 at 17:26
 2021-04-11, 19:18 #20 xilman Bamboozled!     "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 2·72·109 Posts To check for divisibility by 7, 11 and 13 simultaneously use the rule-of-eleven three digits at a time and examine the result. I quite often use this to check primality of small numbers (<30030) without needing to use a calculator. If it passes this check, and the simple ones for 2, 3 and 5, mental trial division by 17, 19, 23 and 29 is straightforward and reaches 6469693230. Checking divisibility by 37 is easy enough by casting out the 999s. An additional mental division by 31 suffices to 7420738134810 (which is somewhat over 7 billion). Long before that I tend to resort to computer assistance.
2021-04-12, 10:30   #21
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

101001101110102 Posts

Quote:
 Originally Posted by xilman To check for divisibility by 7, 11 and 13 simultaneously use the rule-of-eleven three digits at a time and examine the result. I quite often use this to check primality of small numbers (<30030) without needing to use a calculator. If it passes this check, and the simple ones for 2, 3 and 5, mental trial division by 17, 19, 23 and 29 is straightforward and reaches 6469693230. Checking divisibility by 37 is easy enough by casting out the 999s. An additional mental division by 31 suffices to 7420738134810 (which is somewhat over 7 billion). Long before that I tend to resort to computer assistance.
I realise that is profoundly misleading, not to say wrong.

37# is certainly >7.4 billion, and so on, but the procedure outlined work only to 41^2-1 = 1680 as a primality test. It filters out 85% of composites in the limit.

Still, I find it useful.

 2021-04-21, 06:44 #22 mersenneNoob   "Nigel" Apr 2021 168 Posts Another 129 digit number Code: 483100240063213823403065506870079481290504898733191281212060160586898805944701565058228233588987690426223309716587384614909677337 is my second 129-digit challenge number. If factors are found put them on factordb. Last fiddled with by retina on 2021-04-21 at 06:48 Reason: More yucky horizontal scrolling, changed to a code box. You can fix this yourself

 Similar Threads Thread Thread Starter Forum Replies Last Post Titteris Factoring 65 2019-02-15 01:00 pepi37 Math 10 2018-03-02 16:50 sweety439 Factoring 9 2016-12-21 21:22 Unregistered Software 3 2004-03-03 19:20

All times are UTC. The time now is 10:25.

Tue May 11 10:25:15 UTC 2021 up 33 days, 5:06, 1 user, load averages: 1.49, 1.51, 1.56