4 ms·
In Python: q = 10000000000 n = 11111111111111111111 factors = [3, 3, 11, 41, 101, 271, 3541, 9091, 27961] q10 = q/10 bits = len(factors) #pri
by Someone 11y ago
In Python:
q = 10000000000
n = 11111111111111111111
factors = [3, 3, 11, 41, 101, 271, 3541, 9091, 27961]
q10 = q/10
bits = len(factors)
#print b
#print 11*41*101*271*3541*9091*27961
for i in range(2**bits):
r = 1
s = 1
for j in range(bits):
if i&(1<<j):
r *= factors[j]
else:
s *= factors[j]
# To solve:
# q+2a+2b-1 = r
# q+2a-2b+1 = s
# q+2a = (r+s)/2
# 2b-1 = (r-s)/2
#
# => a = ((r+s)/2 - q) / 2
# => b = (1+(r-s)/2) / 2
#
# r and s are odd, so we do not have to worry much about fractions
two_a = (r+s)/2 - q
if two_a % 1 == 0:
a = two_a / 2
two_b = (r-s)/2 + 1
if two_b %1 == 0:
b = two_b / 2
if (q10 <= a < q) and (q10 <= b < q):
print a, b, b*b-a*a
On my system:
time (./ExcellentNumbers.py | sort -u)
real 0m0.031s
user 0m0.016s
sys 0m0.011s
Beats the 1m40 seconds the optimisation got in C, but this is cheating, as it hard-codes the factorisation. Doing that the proper way should not add minutes, though.
If you want to tackle factoring large repunits, do make use of the fact that a repunit containing pq digits can be trivially factored as either a p-digit reunite and a 1000…0001000…0001… one or a q-digit repunit. For example, we have:
111111111111 = 11 x 10101010101
= 111 x 1001001001
= 1111 x 100010001
= 111111 x 1000001
With those factors in hand, find a few others by taking GCDs of other factors, or by ‘randomly’ dividing numbers. For example, 1111 does not share a factor with 111, so 100010001 must be divisible by 111.
Edit: tried the 42-digit one. It has:
q = 1000000000000000000000
n = 111111111111111111111111111111111111111111
factors [3,7,7,11,13,37,43,127,239,1933,2689,4649,459691,909091,10838689]
Times on my system to find 335 solutions:
real 0m0.219s
user 0m0.185s
sys 0m0.022s
I think that is a bit faster than what you had.
And you may want to loosen the range of values for b, replacing
(q10 <= b < q)
by
(0 <= b < q)
- te 11y agoThis is seriously awesome. Got to love when you make a blog post about a 20x speedup, and the internet returns the favor with an Infx speedup.
- nanis 11y agoYou need to keep in mind, though, that the factors of 9999999999999999999999999999999999999999 need to be found somehow. Sure, one can "cheat" and use the factors of 1111111111111111111111111111111111111111 and a couple of extra 3s, but, then you have avoided the problem. That is fine normally, but just not an apples-to-apples comparison.
- Someone 11y agoFirstly, lots of work has been done here. See for example http://www.worldofnumbers.com/repunits.htm http://www.worldofnumbers.com/repunits.htm (factorizations of repunits up to 8580 digits). I also think repunits are, in general, easier to factor because ones that do not have a prime number of digits have obvious divisors. Certainly, rep units of up to 50 digits are factored easily (Google a bignum factorization program online, and try for yourself) Even disregarding that, the original code computed a square root about sqrt(n) times (that's why its running time went up by a factor of 10 for every two digits added). Even without using advanced factoring algorithms, you can factor that number using, at the very most, sqrt(n) trial divisions.
- user2994cb 11y agoYour 42 digit result isn't quite right - you need another 2 factors of 3. With that, there are 999 different solutions (Sinan should be pleased with that). I have a blog entry about a similar solution at https://matthewarcus.wordpress.com/2016/01/16/excellent-numbers/ https://matthewarcus.wordpress.com/2016/01/16/excellent-numb...