mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-08-29, 06:41   #12
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2×3×29×67 Posts
Default

Quote:
Originally Posted by fatphil View Post
Just updated with some info about the direction I headed in, so you don't need to reinvent the wheel. It looks like I may have to reinvent some of my factors, as I can't find the window I was working in!

But tonight is sauna night, so I'm happily tucked away there for the rest of the evening.
pcl@nut:~/Desktop$ ecm -maxmem 2048 1000000 < composites.txt
GMP-ECM 7.0.4 [configured with GMP 6.2.1, --enable-asm-redc] [ECM]
Input number is 9614319269...4094423041 (82177 digits)
Using B1=1000000, B2=914058610, polynomial Dickson(3), sigma=0:4416831086328320100
Step 1 took 27856254ms
Step 2 took 7836917ms
********** Factor found in step 2: 2749553154323378809339903
Found prime factor of 25 digits: 2749553154323378809339903
Composite cofactor 3496...9247 has 82153 digits


The above has been lightly edited. Note it was found on the first curve tried.
xilman is offline   Reply With Quote
Old 2022-08-29, 07:40   #13
fatphil
 
fatphil's Avatar
 
May 2003

3×5×17 Posts
Default

Quote:
Originally Posted by xilman View Post
Step 1 took 27856254ms
Step 2 took 7836917ms
Found prime factor of 25 digits: 2749553154323378809339903
Wow - thanks! Gmp-ecm never stops impressing me. I'm beginning to regret my strategy of starting with a small B1, I'm still on my 174th failing curve with B1 up to 35000...
I don't think I'll bother with the 160kdigit next term, it's probably time to look more closely at the algebra.
fatphil is offline   Reply With Quote
Old 2022-08-29, 09:16   #14
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2D8A16 Posts
Default

Quote:
Originally Posted by fatphil View Post
I didn't do P+/-1 because I was prepared to just let ECM run, and with 100 curves, now 125, the Hasse coverage should have pulled out something that was in range of P+/-1.
FWIW

? factor(2749553154323378809339902)
%1 =
[ 2 1]

[ 3 1]

[ 232357 1]

[ 423601 1]

[4655840911681 1]

? factor(2749553154323378809339904)
%2 =
[ 2 18]

[ 313 1]

[ 113083 1]

[296333355629 1]

xilman is offline   Reply With Quote
Old 2022-08-29, 14:08   #15
fatphil
 
fatphil's Avatar
 
May 2003

25510 Posts
Default

Quote:
Originally Posted by xilman View Post
Note it was found on the first curve tried.
It's nice when things drop out just at the ideal moment. For instance, I was just about to give up on this number:

Run 100 out of 100:
Using B1=10315491, B2=10315490-35133066160, polynomial Dickson(12), sigma=1:1661695324
Step 1 took 12909ms
Step 2 took 6496ms
********** Factor found in step 2: 125960894984050328038716298487435392001
Found prime factor of 39 digits: 125960894984050328038716298487435392001
Prime cofactor 260850953670702126641628144218597843056427843281352119936811457220827426196135100642146995717121 has 96 digits

Bosh!

All the known factors in the numerators are now up at http://fatphil.org/maths/sqrt_cf/sqrt5.html

I'll need to read up on the denominators a bit more before deciding if there's anything more to discover.
fatphil is offline   Reply With Quote
Old 2022-08-29, 14:48   #16
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2D8A16 Posts
Default

Quote:
Originally Posted by fatphil View Post
It's nice when things drop out just at the ideal moment. For instance, I was just about to give up on this number:

Run 100 out of 100:
Using B1=10315491, B2=10315490-35133066160, polynomial Dickson(12), sigma=1:1661695324
Step 1 took 12909ms
Step 2 took 6496ms
********** Factor found in step 2: 125960894984050328038716298487435392001
Found prime factor of 39 digits: 125960894984050328038716298487435392001
Prime cofactor 260850953670702126641628144218597843056427843281352119936811457220827426196135100642146995717121 has 96 digits

Bosh!

All the known factors in the numerators are now up at http://fatphil.org/maths/sqrt_cf/sqrt5.html
]I am prepared to spend a day or two on your 160K-digit composite if you think it worthwhile.

You should have switched to GNFS for the C135 IMO.

Last fiddled with by xilman on 2022-08-29 at 14:49
xilman is offline   Reply With Quote
Old 2022-08-29, 16:11   #17
fatphil
 
fatphil's Avatar
 
May 2003

3×5×17 Posts
Default

Quote:
Originally Posted by xilman View Post
]I am prepared to spend a day or two on your 160K-digit composite if you think it worthwhile.

You should have switched to GNFS for the C135 IMO.
Now I've worked out the algebraic structure, these are just a^n+b^n and a^n-b^n sequences. I don't think there's any need to hunt for factors any more, at least on the numerator side, but I'll continue to fill out a decent sized table of factors on the denominator side, mostly for schitzengiggles. A deeper hunt for PRPs on the denominator side should be done still.
fatphil is offline   Reply With Quote
Old 2022-08-29, 17:18   #18
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

3·251 Posts
Default

I just checked, and your 82177-digit number is Lucas(393216)/2. Therefore, it's divisible by Lucas(131072)

Last fiddled with by Stargate38 on 2022-08-29 at 17:20 Reason: forgot to mention which number
Stargate38 is offline   Reply With Quote
Old 2022-08-29, 17:59   #19
fatphil
 
fatphil's Avatar
 
May 2003

3·5·17 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
I just checked, and your 82177-digit number is Lucas(393216)/2. Therefore, it's divisible by Lucas(131072)
In that case all of them will be divisible by smaller Lucas numbers, and therefore none can be prime.

Congrats, you've solved the first half of the conjecture!

Edit: how did you work out it was half-a-lucas?

Last fiddled with by fatphil on 2022-08-29 at 18:00
fatphil is offline   Reply With Quote
Old 2022-08-29, 18:29   #20
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

13618 Posts
Default

I copy-pasted the full number into FactorDB. After hitting "Factorize", I then clicked on the link under where it says "number". Since the number was already on the DB, it simplified it to the shortest known formula.

Last fiddled with by Stargate38 on 2022-08-29 at 18:30
Stargate38 is offline   Reply With Quote
Old 2022-08-29, 19:07   #21
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

11000010011102 Posts
Default

The fundamental unit \epsilon > 1 of the ring of algebraic integers in Q(sqrt(5)) is the "golden ratio" \frac{1+\sqrt{5}}{2}.

We have \epsilon^{n}\;=\;\frac{L_{n}\;+\;F_{n}\sqrt{5}}{2}.

Thus, the Lucas and Fibonacci numbers satisfy L_{n}^{2}\;-\;5F_{n}^{2}\;=\;4\cdot(-1)^{n}.

Both Ln and Fn are even when n is divisible by 3. The numerators and denominators of the SCF for sqrt(5) (solutions to x2 - 5y2 = ยฑ1) are thus x = (1/2)L3k and y = (1/2)F3k.

Now L3k is divisible by Ld for every divisor of 3k whose cofactor is odd, and F3k is divisible by Fd for every divisor d of 3k.

You have to be a little careful in translating this to results about (1/2)L3k and (1/2)F3k.
Dr Sardonicus is offline   Reply With Quote
Old 2022-08-29, 19:08   #22
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2×3×29×67 Posts
Default

Quote:
Originally Posted by fatphil View Post
Now I've worked out the algebraic structure, these are just a^n+b^n and a^n-b^n sequences. I don't think there's any need to hunt for factors any more, at least on the numerator side, but I'll continue to fill out a decent sized table of factors on the denominator side, mostly for schitzengiggles. A deeper hunt for PRPs on the denominator side should be done still.
Let me know how (if) I can help.
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Observations of Wieferich primes and Wieferich-1 friendly club hansl Math 3 2020-09-02 10:40
More User friendly main page Sutton Shin mersennewiki 0 2012-09-29 08:03
Family Friendly Foraging davieddy Soap Box 9 2012-07-13 05:39
User Friendly davieddy Lounge 1 2011-06-10 18:42
Making the forum more dial-up friendly... Xyzzy Lounge 11 2003-05-15 08:38

All times are UTC. The time now is 15:37.


Thu Feb 2 15:37:16 UTC 2023 up 168 days, 13:05, 1 user, load averages: 0.95, 1.05, 1.02

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

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”