mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-03-23, 18:36   #1024
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

7·97 Posts
Default

Quote:
Originally Posted by warachwe View Post
I tried a few number of exponents on base 7.
So far 1987441237556775=3^5 · 5^2 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 37 · 41 is lowest odd n I found that s(7^n) is abundant, but with primes <105.

WOW !
You have found an abundant one for a base which is a prime number !
Congratulations !
This result is wonderful and makes me dizzy !

Unfortunately, I am completely unable to verify this result with the methods at my disposal.
The size of the exponent is scary and also the fact that you have to consider the prime numbers < 10^5 instead of 10^4.
This slows down the programs very strongly ...

I let Happy's C programs run. We will try to find the smallest possible exponent.
But I am worried when I see the size of your exponent !

garambois is online now   Reply With Quote
Old 2021-03-23, 22:20   #1025
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2·379 Posts
Default

Quote:
Originally Posted by warachwe View Post
I tried a few number of exponents on base 7.
So far 1987441237556775=3^5 · 5^2 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 37 · 41 is lowest odd n I found that s(7^n) is abundant, but with primes <105.
Quote:
Originally Posted by garambois View Post
WOW !
Unfortunately, I am completely unable to verify this result with the methods at my disposal.
The size of the exponent is scary and also the fact that you have to consider the prime numbers < 10^5 instead of 10^4.
This slows down the programs very strongly ...
@warachwe: Do you have the abundant factors available? We could verify divisibility (by index 1) and abundance using those, as that would be much quicker than dividing by all primes < 10^5. But yes, let's hope for a smaller one too.
Happy5214 is offline   Reply With Quote
Old 2021-03-24, 07:10   #1026
warachwe
 
Aug 2020

19 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
@warachwe: Do you have the abundant factors available? We could verify divisibility (by index 1) and abundance using those, as that would be much quicker than dividing by all primes < 10^5. But yes, let's hope for a smaller one too.
Code:
3^5 * 19^2 * 29^2 * 31 * 37^2 * 47 * 59 * 83 * 103 * 109 * 131 * 139 * 199 * 223 * 271 * 307 * 419 * 523 * 613 * 647 * 691 * 701 * 757 * 811 * 859 * 1063 * 1093 * 1123 * 1151 * 1231 * 1259 * 1381 * 1429 * 1459 * 1481 * 1483 * 1531 * 1559 * 1567 * 1621 * 1783 * 1873 * 1951 * 2269 * 2377 * 2551 * 2707 * 2801 * 2887 * 2971 * 3061 * 3079 * 3083 * 3109 * 3191 * 3257 * 3307 * 3331 * 3631 * 3727 * 3911 * 4003 * 4051 * 4219 * 4591 * 4621 * 4733 * 4931 * 5347 * 5659 * 5743 * 5851 * 6151 * 6217 * 6271 * 6301 * 6661 * 6917 * 6971 * 7177 * 7411 * 7541 * 7591 * 7867 * 8009 * 8101 * 8263 * 8933 * 9103 * 9109 * 9349 * 10099 * 10531 * 10949 * 11287 * 11311 * 11731 * 12211 * 12301 * 12377 * 12433 * 12547 * 13469 * 14009 * 14251 * 14327 * 14653 * 14821 * 14951 * 15121 * 15319 * 15391 * 15541 * 15661 * 15733 * 15913 * 15991 * 16651 * 16763 * 16831 * 17021 * 17443 * 18451 * 18701 * 19609 * 19927 * 20011 * 20021 * 20359 * 20747 * 20749 * 21737 * 22543 * 22621 * 22679 * 23371 * 25117 * 25309 * 26731 * 27551 * 28843 * 29173 * 29251 * 29717 * 31051 * 31081 * 32063 * 32191 * 33151 * 33211 * 33301 * 33967 * 34273 * 35531 * 35671 * 35729 * 35803 * 36671 * 38611 * 39443 * 40591 * 41413 * 42979 * 43291 * 44371 * 46171 * 46399 * 47881 * 48907 * 50923 * 51679 * 51949 * 52027 * 52837 * 52973 * 54367 * 56167 * 56701 * 58631 * 59053 * 59509 * 59671 * 60089 * 60589 * 60611 * 60763 * 62701 * 64091 * 65269 * 65437 * 65551 * 67489 * 67651 * 68311 * 69191 * 69499 * 70111 * 70841 * 71341 * 71707 * 72931 * 73951 * 75401 * 76039 * 76561 * 77141 * 77419 * 78541 * 78737 * 80191 * 81001 * 81901 * 81919 * 84391 * 84457 * 84871 * 86131 * 87211 * 92251 * 94351 * 94771 * 95701 * 97021 * 98533 * 99877
I wrote a program to check for this n only, and then trial factor primes <10^5 on (7n-1)/6.
I am not quite sure with my coding skill. I would really appreciate if someone can double check it.
warachwe is offline   Reply With Quote
Old 2021-03-24, 13:26   #1027
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

13668 Posts
Default

Quote:
Originally Posted by warachwe View Post
Code:
3^5 * 19^2 * 29^2 * 31 * 37^2 * 47 * 59 * 83 * 103 * 109 * 131 * 139 * 199 * 223 * 271 * 307 * 419 * 523 * 613 * 647 * 691 * 701 * 757 * 811 * 859 * 1063 * 1093 * 1123 * 1151 * 1231 * 1259 * 1381 * 1429 * 1459 * 1481 * 1483 * 1531 * 1559 * 1567 * 1621 * 1783 * 1873 * 1951 * 2269 * 2377 * 2551 * 2707 * 2801 * 2887 * 2971 * 3061 * 3079 * 3083 * 3109 * 3191 * 3257 * 3307 * 3331 * 3631 * 3727 * 3911 * 4003 * 4051 * 4219 * 4591 * 4621 * 4733 * 4931 * 5347 * 5659 * 5743 * 5851 * 6151 * 6217 * 6271 * 6301 * 6661 * 6917 * 6971 * 7177 * 7411 * 7541 * 7591 * 7867 * 8009 * 8101 * 8263 * 8933 * 9103 * 9109 * 9349 * 10099 * 10531 * 10949 * 11287 * 11311 * 11731 * 12211 * 12301 * 12377 * 12433 * 12547 * 13469 * 14009 * 14251 * 14327 * 14653 * 14821 * 14951 * 15121 * 15319 * 15391 * 15541 * 15661 * 15733 * 15913 * 15991 * 16651 * 16763 * 16831 * 17021 * 17443 * 18451 * 18701 * 19609 * 19927 * 20011 * 20021 * 20359 * 20747 * 20749 * 21737 * 22543 * 22621 * 22679 * 23371 * 25117 * 25309 * 26731 * 27551 * 28843 * 29173 * 29251 * 29717 * 31051 * 31081 * 32063 * 32191 * 33151 * 33211 * 33301 * 33967 * 34273 * 35531 * 35671 * 35729 * 35803 * 36671 * 38611 * 39443 * 40591 * 41413 * 42979 * 43291 * 44371 * 46171 * 46399 * 47881 * 48907 * 50923 * 51679 * 51949 * 52027 * 52837 * 52973 * 54367 * 56167 * 56701 * 58631 * 59053 * 59509 * 59671 * 60089 * 60589 * 60611 * 60763 * 62701 * 64091 * 65269 * 65437 * 65551 * 67489 * 67651 * 68311 * 69191 * 69499 * 70111 * 70841 * 71341 * 71707 * 72931 * 73951 * 75401 * 76039 * 76561 * 77141 * 77419 * 78541 * 78737 * 80191 * 81001 * 81901 * 81919 * 84391 * 84457 * 84871 * 86131 * 87211 * 92251 * 94351 * 94771 * 95701 * 97021 * 98533 * 99877
I wrote a program to check for this n only, and then trial factor primes <10^5 on (7n-1)/6.
I am not quite sure with my coding skill. I would really appreciate if someone can double check it.
Did you use GMP for this? I tried to retrofit the program I wrote for Jean-Luc by just using the factors you posted, but I actually overflowed GMP with the size of the number. :/ I did verify the abundance of those factors with PARI/GP. If it's not in an unusual language, do you mind posting your code so we can validate that for correctness? It's probably our best chance unless someone has a base 7 Cunningham TF algorithm. It's bigger than even GIMPS's numbers!
Happy5214 is offline   Reply With Quote
Old 2021-03-24, 14:24   #1028
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

22×163 Posts
Default

We can do that more efficiently. Since we have \[\sigma(p^n)=\sum^{n-1}_{i=0}{p^i}=\frac{p^n-1}{p-1}\] for prime \(p\), we can check for divisors of \(\sigma(p)\) as such: compute \(p^n \mod (p - 1) \cdot f\), where \(f\) is the factor to be checked. If the result is 1, \(f\) divides \(\sigma(p^n)\). Since modular exponentiation is cheap, we can do it extremely fast.

Last fiddled with by kruoli on 2021-03-24 at 14:28 Reason: Removed bogus letters. Corrected formula.
kruoli is online now   Reply With Quote
Old 2021-03-24, 15:43   #1029
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2F616 Posts
Default

Quote:
Originally Posted by kruoli View Post
We can do that more efficiently. Since we have \[\sigma(p^n)=\sum^{n-1}_{i=0}{p^i}=\frac{p^n-1}{p-1}\] for prime \(p\), we can check for divisors of \(\sigma(p)\) as such: compute \(p^n \mod (p - 1) \cdot f\), where \(f\) is the factor to be checked. If the result is 1, \(f\) divides \(\sigma(p^n)\). Since modular exponentiation is cheap, we can do it extremely fast.
Thank you for that, Oliver. Using that formula, I have validated all of warachwe's factors. Program attached.
Attached Files
File Type: gz powerAbundance2.tar.gz (1.1 KB, 30 views)
Happy5214 is offline   Reply With Quote
Old 2021-03-24, 19:29   #1030
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

12478 Posts
Default

Thank you very much to you for this validation work !
I will examine all of this carefully so that I too can learn how to do this ...
garambois is online now   Reply With Quote
Old 2021-03-24, 19:37   #1031
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2·379 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
Thank you for that, Oliver. Using that formula, I have validated all of warachwe's factors. Program attached.
Quote:
Originally Posted by garambois View Post
Thank you very much to you for this validation work !
I will examine all of this carefully so that I too can learn how to do this ...
I missed 37^2 in that program, and it's a mess editing it for each new validation, so I came up with a single program that can be used for any prime power (attached here). You pass the prime base (it only works with primes right now) and the exponent, and include the factors in a file (one per line, exponents OK), and it will check divisibility and abundance at once, and very quickly too.

Edit: 37^2 does divide, according to the new code, so we're OK there.
Attached Files
File Type: gz verifyPrimePowerAbundance.tar.gz (1.3 KB, 34 views)

Last fiddled with by Happy5214 on 2021-03-24 at 19:42
Happy5214 is offline   Reply With Quote
Old 2021-03-24, 19:53   #1032
warachwe
 
Aug 2020

238 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
Did you use GMP for this? I tried to retrofit the program I wrote for Jean-Luc by just using the factors you posted, but I actually overflowed GMP with the size of the number. :/ I did verify the abundance of those factors with PARI/GP. If it's not in an unusual language, do you mind posting your code so we can validate that for correctness? It's probably our best chance unless someone has a base 7 Cunningham TF algorithm. It's bigger than even GIMPS's numbers!
I use the same method that @kruoli point out, and thank you very much for checking those factors.
warachwe is offline   Reply With Quote
Old 2021-03-24, 21:08   #1033
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

61×97 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
I missed 37^2 in that program, and it's a mess editing it for each new validation, so I came up with a single program that can be used for any prime power (attached here). You pass the prime base (it only works with primes right now) and the exponent, and include the factors in a file (one per line, exponents OK), and it will check divisibility and abundance at once, and very quickly too.

Edit: 37^2 does divide, according to the new code, so we're OK there.
Does this check primality of the base for using the new formula?
henryzz is offline   Reply With Quote
Old 2021-03-24, 21:19   #1034
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

2×379 Posts
Default

Quote:
Originally Posted by henryzz View Post
Does this check primality of the base for using the new formula?
Given the name, audience, use case, and lack of actual values to use it on, I figured it was unnecessary. I guess not. I'll add it (which is, what, 4 lines?) when I get back to my main computer tomorrow. Until then, do not pass it a composite base.

Last fiddled with by Happy5214 on 2021-03-24 at 21:20
Happy5214 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Broken aliquot sequences fivemack FactorDB 46 2021-02-21 10:46
Broken aliquot sequences schickel FactorDB 18 2013-06-12 16:09
A new theorem about aliquot sequences garambois Aliquot Sequences 34 2012-06-10 21:53
poaching aliquot sequences... Andi47 FactorDB 21 2011-12-29 21:11
New article on aliquot sequences schickel mersennewiki 0 2008-12-30 07:07

All times are UTC. The time now is 08:29.


Wed Oct 20 08:29:05 UTC 2021 up 89 days, 2:58, 0 users, load averages: 3.27, 3.04, 2.93

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.