Hacker News new | comments | show | ask | jobs | submit login

Given N, introducing q=10^N, they are looking for a and b in [0,q) such that

  (q+2a)^2-(2b-1)^2 = q^2-1
For example, for N=1, q=10, given 18^2 - 15^2 = 99, we find a solution with a=4, b=8: 48

That suggests using https://en.m.wikipedia.org/wiki/Midpoint_circle_algorithm#Va... to get rid of that pesky square root (circle drawing uses sums of squares, but I think that is trivially adjusted for)

I also think it is worthwhile to extend this to other bases, as it more easily produces more examples to look at for discovering structure, and gets rid of the arbitrarily chosen number 10.

Edit: for those needing some explanation how to get at that claim:

  let q > 0
(they pick q=10, q=100, q=1000, but this generalises this)

Assume

  aq+b = b^2 - a^2 for some a,b in [0,q]
in other words: b^2-a^2, written in base q, is ab

Then:

  b^2 - a^2 = qa+b                          <=> (bring all b’s to the left, all else to the right)
  b^2 - b = qa + a^2                        <=> (factor)
  b(b-1)  = a(a+q)                          <=> (using (p+q)(p-q) = p^2-q^2)
  (b-1/2)^2 - (1/2)^2 = (a+q/2)^2 - (q/2)^2 <=> (multiply by 4 on both sides)
  (2b-1)^2 - 1 = (2a+q)^2 - q^2             <=> (bring all a’s and all b’s to the right)
  q^2 - 1 = (2a+q)^2 - (2b-1)^2             <=> (switch sides; slight rewrite)
  (q+2a)^2 - (2b-1)^2 = q^2-1
Edit 2: for large q, it probably is faster to do the (p+q)(p-q) = p^2-q^2 trick again (apologies for naming the free variable q the same as the q introduced earlier), and get:

  (q+2a+2b-1)(q+2a-2b+1) = q^2-1
Next, factor q^2-1, write all ways to write it as product of integers, and check each case for integer solutions for a and b in the right range. For example, for q=10, we have:

  99 = 1x99 = 3x33 = 9x11 = 11x9 = 33x3 = 99x1, so we solve 6 systems (I guess one easily discard half of them on arguments of the p+q part being larger than the p-q part, but that’s peanuts) of two linear equations in two variables:

  / q+2a+2b-1 =  1
  \ q+2a-2b+1 = 99

  / q+2a+2b-1 =  3
  \ q+2a-2b+1 = 33

  …

  / q+2a+2b-1 = 99
  \ q+2a-2b+1 =  1
This also suggests that the number of solutions with d base q digits for a and b is correlated with the number of integers that divide q^2-1. That would link it to http://oeis.org/A000010.

Edit 3: and for the 10^N case, one might consider http://oeis.org/A095370. For example, the 62-digit number 1111…1111 has only 5 prime factors. You have to add 2 factors of 3 to get 9999…9999, so 10^62-1 can be written as product of two integers in 2^7 ways => only 2^6 = 64 equations to solve.




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)


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.


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.


Firstly, lots of work has been done here. See for example 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.


I tried out the arithmetic, and it works. So, this transforms the problem drastically. Nice insight.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: