mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2021-04-10, 02:02   #12
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts
Default

Quote:
Originally Posted by charybdis View Post
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
a1call is offline   Reply With Quote
Old 2021-04-10, 02:57   #13
mersenneNoob
 
"Nigel"
Apr 2021

11102 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
mersenneNoob is offline   Reply With Quote
Old 2021-04-10, 12:47   #14
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

23×34×7 Posts
Default

Quote:
Originally Posted by a1call View Post
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!
Dr Sardonicus is offline   Reply With Quote
Old 2021-04-11, 10:51   #15
mersenneNoob
 
"Nigel"
Apr 2021

2·7 Posts
Default OP=??

Why did you all start calling the number OP-number?
mersenneNoob is offline   Reply With Quote
Old 2021-04-11, 10:54   #16
slandrum
 
Jan 2021
California

22·17 Posts
Default

Quote:
Originally Posted by mersenneNoob View Post
Why did you all start calling the number OP-number?
OP is Original Poster, the person who started the thread - in other words you.
slandrum is offline   Reply With Quote
Old 2021-04-11, 15:59   #17
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

453610 Posts
Default

Quote:
Originally Posted by a1call View Post
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).
Dr Sardonicus is offline   Reply With Quote
Old 2021-04-11, 16:43   #18
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts
Default

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
a1call is offline   Reply With Quote
Old 2021-04-11, 17:24   #19
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

223448 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2021-04-11, 19:18   #20
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

29BA16 Posts
Default

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.
xilman is offline   Reply With Quote
Old 2021-04-12, 10:30   #21
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·72·109 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
xilman is offline   Reply With Quote
Old 2021-04-21, 06:44   #22
mersenneNoob
 
"Nigel"
Apr 2021

2×7 Posts
Default 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
mersenneNoob is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring a 172-digit number. Titteris Factoring 65 2019-02-15 01:00
Generating from 16 to 35 digit number in row (+1) pepi37 Math 10 2018-03-02 16:50
Factor a 108-digit number sweety439 Factoring 9 2016-12-21 21:22
10,000,000 digit number Unregistered Software 3 2004-03-03 19:20

All times are UTC. The time now is 21:02.

Mon May 10 21:02:05 UTC 2021 up 32 days, 15:42, 1 user, load averages: 6.63, 6.15, 5.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.