## Torn Numbers

### September 16, 2014

I don’t know any way to solve this problem other than brute force. Here’s a function that determines if a number can be torn:

`(define (torn? n)`

(define (square n) (* n n))

(let loop ((ten-power 10))

(if (< n ten-power) #f

(let ((a (quotient n ten-power))

(b (modulo n ten-power)))

(if (= (square (+ a b)) n) #t

(loop (* ten-power 10)))))))

And here it is in action:

`> (do ((n 10 (+ n 1))) (#f)`

(when (torn? n) (display n) (newline)))

81

100

2025

3025

9801

10000

88209

494209

998001

1000000

4941729

7441984

23804641

24502500

25502500

28005264

52881984

60481729

99980001

100000000

You can run the program at http://programmingpraxis.codepad.org/neU69dwU, and see more terms of the sequence at A102766.

In Python.

You can reduce brute force x10 but must solve one quadratic equation for each digit partition (but, probably it can reduce too).

For only AABBB partition only 10000 checks (instead 100000 checks).

(10000 complete checks, checking for Torn number using `isTorn` is only taken 1290 times)

(cannot edit posts? :/ )

(arghhh!)

Obviously, computing better the quadratic solution (e.g. I’m using `round` instead one error bound) it can be reduced; also, quadratic domain could be inspected to inspect only regions with possible solutions. But not like trivial…

Java

Perl version – note that I’m avoiding multiplication except in the output!

@JoseJuan: Your solution misses some torn numbers.

A simple optimization over the suggested solution is to immediately filter out numbers which aren’t perfect squares:

On this machine using Kawa, the original solution takes about 4 minutes 45 seconds to check all numbers from 10 to 100 million; substituting this one instead finishes in 45 seconds.

Computing all Torn numbers in Haskell.

Another nice problem. We want a(k+1) + b = (a+b)^2, with k = 9,99,999 etc. Put c = a+b, and substitute c-a for b, rearrange to ak = c(c-1) ie. c(c-1) mod k == 0. Maximum possible value for c is k+1 (when a == k+1 and b == 0). Also, k is a multiple of 9, therefore either c or c-1 is also (since they are coprime), so we don’t have to try every value for c. Results are produced according to tear position, so sort the output:

Nice to see 1729 in there. We could do some strength reduction etc. but doesn’t seem to gain much in Python.

Yes @matthew I see it also using `n = q^2 = (a + b)^2 = a + 10^x b` then substracting equations `n = a + 10^x b` and `q = a + b` is `n – q = 999..999 b`.

Indeed, and having another look this morning: for a given k, ak = c(c-1) is a Diophantine equation of the simple form Ax^2 + Bx + Cy = 0, which can then be solved using general methods (eg. see http://www.alpertron.com.ar/QUAD.HTM, which also has an handy online solver – for k = 999, we get (with a couple of simple cases) x = 999 u + 297, y = 999 u^2 + 593 u + 88 or x = 999 u + 703, y = 999 u^2 + 1405 u + 494 which gives our 88209 and 494209 solutions respectively for u = 0.

(I cannot post my code here)

Using previous checker for squares code here

Actually, I’m not sure if there is a general method – that solver seems to be doing essentially what my Python program does (it has handy “show derivation steps” feature), though we can generalize the solution found.

C# Solution:

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

Thread myThread;

private void button1_Click(object sender, EventArgs e)

{

lstTornNumbers.Items.Clear();

label1.Text = "Current number: " + 0;

myThread = new Thread(CalculateTornNumbers);

myThread.Start();

button1.Enabled = false;

button2.Enabled = true;

}

void CalculateTornNumbers()

{

int i = 0;

while(myThread.ThreadState != ThreadState.AbortRequested)

{

label1.Invoke((MethodInvoker)delegate

{

label1.Text = "Current number: " + i;

});

int locResult;

if (int.TryParse(Math.Sqrt(i).ToString(), out locResult))

{

for(int x =1;x<i.ToString().Length;x++)

{

int a = Convert.ToInt32(i.ToString().Substring(0, x));

int b = Convert.ToInt32(i.ToString().Substring(x, i.ToString().Length - x));

if ((a + b) == locResult)

{

lstTornNumbers.Invoke((MethodInvoker) delegate

{

ListViewItem myItem = new ListViewItem(new string[] { i.ToString(), a.ToString(), b.ToString() });

lstTornNumbers.Items.Add(myItem);

lstTornNumbers.Refresh();

});

}

}

}

i++;

}

}

`private void button2_Click(object sender, EventArgs e)`

{

myThread.Abort();

button1.Enabled = true;

button2.Enabled = false;

}

}

</code

Not efficient but works

python version

uses a couple optimizations:

1. only checks perfect squares

2. uses (n + 1)**2 = n**2 + (2*n + 1) instead of squaring root_n

in the loop

3. if n has d digits, the left part, a, has at most (d+1)//2 digits.

Or, conversely, the right hand part, b, has at least d//2 digits.

4. both parts have to be less than root_n

5. root_n % 9 must be 0 or 1 (see matthew’s solution above)

Without matthew’s optimization, it would calculate torn(1e15) in about 55 seconds. The optimization dropped that to about 15 seconds. Changing a,b = divmod(n, p) to b = n % p and a = n //p shaved another 2 seconds off.

Profiling showed that the inner “while b < root_n" loop runs an average of 1.1 times per n.

@MIke: nice. Your solution seems to run about the same speed as mine when generating all torn numbers, though it’s faster for generating up to a limit (7 secs vs. 20 secs up to 10^15) – my program generates the actual solutions fairly quickly, but then spends most of its time checking there aren’t any more. Maybe I can improve my bounds checking, but it’s not obvious to me just how.

@Matthew: Looking at your code again, I tried to find better ways to initialize and increment the value of c. For example, if c*c has i+1 digits, then c has at least (i+1)//2 digits. Or c could be initialized to the first value > sqrt(k+1), such that c%9 ==0.

Then it occurred to me that if c(c-1) % k == 0 then c(c-1) % bf(k) == 0, where bf(k) is the biggest factor of k. So, c can be initialized to and incremented by bf(k). This speeds up the search considerably. It now calculates torn(15) in 0.5 seconds, and torn(18) in 2 seconds. (At torn(19), my table of primes runs out so I didn’t go any further.)

Here’s the code:

Turns out (pow(10,19)-1)//9 is prime, so there aren’t any torn numbers for i = 19.

@Mike: That’s brilliant – and it makes me realize we can go further still: we want c(c-1) = ak. Suppose d is a divisor of k and suppose it’s coprime to e = k//d, then if we can find x and y such that xe – yd = 1, then we have a = xy and c = xe. But we can solve xe -yd = 1 with the extended Euclidean algorithm (and we can find a solution just when d and e are indeed coprime). So the problem comes down to finding the divisors of k – and there are some tricks we can use when k is of the form 9….9). Here’s a program that doesn’t use any tricks:

The outputs don’t come out in order, but sorting them we get:

The numbers come in pairs corresponding to the 2 solutions to Jose’s quadratic equation – and also to divisor pair d and k//d, so there are some more simplifications that can be done there (and it would be nice to get rid of that special case for 10…0).

OK, so here’s another version:

Still nothing fancy for finding divisors, though now we only check odd numbers (since k is odd) and we only iterate up to sqrt(k), but we get two solutions each time around. Looks like divisors are relevant to todays problem too.