3 ms·

Interesting idea. Thank you. I'll try that out.

by nanis 11y ago

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 ago
  This 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 ago
    You 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 ago
      Firstly, 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 ago
  Your 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...

Interesting idea. Thank you. I'll try that out.

by nanis 11y ago

Interesting idea. Thank you. I'll try that out.

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 ago
This 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 ago
  You 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 ago
    Firstly, 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 ago
Your 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...