Aliquot sequences that start on the integer powers n^i

[garambois]

Originally Posted by warachwe

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 <10⁵.

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 !

[Happy5214]

Originally Posted by warachwe

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 <10⁵.

Originally Posted by garambois

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.

[warachwe]

Originally Posted by Happy5214

@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.

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 (7ⁿ-1)/6.
I am not quite sure with my coding skill. I would really appreciate if someone can double check it.

[Happy5214]

Originally Posted by warachwe

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 (7ⁿ-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!

[kruoli]

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.

[Happy5214]

Originally Posted by kruoli

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.

[garambois]

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 ...

[Happy5214]

Originally Posted by Happy5214

Thank you for that, Oliver. Using that formula, I have validated all of warachwe's factors. Program attached.

Originally Posted by garambois

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.

[warachwe]

Originally Posted by Happy5214

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.

[henryzz]

Originally Posted by Happy5214

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?

[Happy5214]

Originally Posted by henryzz

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.