collatz sequence^2

[phil1882]

take a number, greater than 1.

if odd, subtract 1, square it.

if even, divide by 2.

2 -> 1

3 -> 4 -> 2

5 -> 8 -> 4

7 -> 36 --> 9 -> 16 -> 8

11 -> 100 -> 25 -> 576 -----> 9

13 -> 144 ----> 9

will this always hit a power of 2?

[bonanova]

No. It happens for most small numbers, but does not happen for example for 27 and most higher odd numbers.

Analysis:

The process removes factors of 2 from even numbers.

If the starting number is a power of 2, this gets us eventually to the value 1, where the process terminates.

The value of 1 cannot be reached by subtracting 1 from and then squaring any odd number greater than 1.

So "terminating" and "reaching a power of 2" are one and the same circumstance.

If the starting even number is not a power of two, the even process stops when an odd number is reached.

So the analysis boils down to noting what the process does to odd numbers greater than 1.

Let n = (2p + 1) p = 1, 2, 3, ... be such a number.

The process strips off the 1 and then squares the result, giving an even number, 4p².

Powers of 2 are then removed, reducing at least to p², but farther, to q² if p itself was even.

So the odd process plus multiple even processes reduce (2p + 1) to q² where q (odd) is either p or p with its even factors removed.

Next, q_i² is subjected to the odd process plus multiple even processes to produce q_i+1².

This process terminates if q_j becomes unity; it diverges otherwise, with q_j increasing without bound.

We can thus track the process by following the successive values of q.

Here are terminating sequences:

...., 65, 33, 17, 9, 5, 3, 1. And 23 leads to 33 ... as well.

...., 63, 31, 15, 7, 3, 1. And 11 leads to 15 ... as well.

First, we can see that starting numbers n of the form 2^m or 1+2^m will immediately produce a power of 2.

Numbers of the form 2^m-1 also lead to powers of 2.

Examples, n=131 leads to q=65; 67 leads to 33; 35 leads to 17; 19 to 9; 11 to 5; 9 to 3.

On the other branch, 127 and 253 lead to 63; 63 and 125 lead to 31; 31 and 61 lead to 15; 23 and 45 to 11; 15 and 29 to 7; and to 3.

All those starting numbers, and of course any multiple of 2 of them will produce powers of 2.

The first divergent number seems to be 27, which leads to q values of 13, 21, 55, 189, 4465, 623007 .... and does not converge.

[bonanova]

Redefine the operations, for simplicity:

En: Remove all the 2 factors from n.
On: Subtract 1. Remove all 2 factors. Square.

Both operations produce an odd number.
We would use E just once: in case n begins as an even number.
Then we just keep applying O until we get 1. Or not. Thus,

Choose a starting number n.

If n is even, En => n'(odd). If n'=1, then n was 2^p and n converges.
If n is odd, repeatedly apply O => n'. If n' ever becomes 1, then n converges.

What even numbers converge?
We know n = 2^p = 2, 4, 8, 16, 32, 64, ... converge.

What odd numbers converge?
Clearly n = 1+2^p = 3, 5, 9, 17, 33, 65, ... converge.

For any convergent odd number, there are infinitely more larger ones that also converge:

Consider:
Let n = 1+2q. Subtract 1: 2q; Remove 2's: q; Square: q².
Let m = 1+4q. Subtract 1: 4q; Remove 2's: q; Square: q².
Same result.
So iff 1+2q converges, 1+4q (and by recursion 1+ (2^p)q where p=1,2,3,...) do as well.

Manually investigate some odd numbers not on the 1+2^p list.

n=7.
Subtract 1 => 6; Remove 2's => 3; Square => 9 = 1+2³. So 7 converges.
7 = 1+2x3.
So 1+(2^p)3 = 7, 13, 25, 49, 97, 193, 385, ... all converge.

n=11.
Subtract 1 => 10; Remove 2's => 5; Square => 25;
Subtract 1 => 24; Remove 2's => 3; Square => 9. So 11 converges.
11 = 1+2x5.
So 1+(2^p)5 = 11, 21, 41, 81, 161, 321, 641, ... all converge

n=13 also converges. (Edit.)

n=15.
Subtract 1 => 14; Remove 2's -> 7; Square => 49;
Subtract 1 => 48; Remove 2's -> 3; Square => 9. So 13 converges.
13 = 1+2x7.
So 1+(2^p)7 = 15, 29, 57, 113, 225, 449, 897, ... all converge.

There is a shorthand for this process: simply note the successive results of O.

Thus,
n= 7 => 9 = 1+2³ so 7 and 13 25 49 97 193 385 ... converge
n=11 => 25, 9 so 11 and 21 41 81 161 321 641 ... converge
n=15 => 49, 9 so 15 and 29 57 113 225 449 897 ... converge

Continuing until we find one that does not converge,

n=19 => 81 26 9 so 19 and 37 73 145 289 577 1153 2305 ... converge

n=21 => 25 9 so 21 and 41 81 161 (repeating the n=11 list) converge

n=23 => 121 225 49 9 so 23 and 45 89 177 353 705 1409 ... converge
n=25 => 9 so 25 and 49 97 193 385 769 1537 3073 6145 ... converge

But then we get one that misbehaves:

n=27 => 169 441 3025 35721 1.99E7 3.88E11 ... ?

We don't know whether this sequence returns to 1.

The numbers get too large to handle exactly as integers.

We do know numbers larger than 27 converge, for example 29:

n=29 => 49 9 so 29 and 57 113 225 449 897 1793 3585 7169 ... converge.

Divergent starting numbers seem isolated, at least for low numbers.

With a simplified definition of the process and some recursion formulas

we have complied a good list of convergent odd numbers.

All the even multiples converge, as well.

If someone with great integer programming skills can resolve the n=27 case,

it would be interesting to know that result.

This is a difficult conjecture for two reasons, at least.

1. The numbers (because of squaring) can get large.
   
2. The recursion formulas give numbers that become
   increasingly sparse as they get big. Even with them,
   an infinite number of individual numbers will have to
   be checked, or at least until one starting number is
   found that diverges.

If anyone is interested to continue this analysis, here are three suggestions.

1. Confirm that n=27 diverges (or not.)
2. Confirm that (-1)+2^p converges, as well as 2^p and 1+2^p.
3. Find other recursion relations.

[phil1882]

i'm fairly certain 27 diverges.

after the first run; if n-1 is not a power of 2, divide by 2 untiill odd, then, take n+1divide by 2 untill odd, and multiply the two.

i get the following.

27

13

21

55

189

4465

623007

6064651907

its pretty clear this will not reach a power of 2. or if it

does it will be quite large.

[plasmid]

Still not a solution, but if I could get a better handle on the function

(n x 2^a + 1) = m²

it might lead to one.

If a number converges to a power of 2 it would then converge to 1 as you keep dividing the power of 2 by 2, as Bonanova pointed out. So one could tackle this question from the other direction: starting at 1, what set of numbers could you reach by applying this algorithm backwards?

Any number n could be preceded by either 2n or by sqrt(n)+1. Call a sequence going in reverse order R(n) where

R(n+1) = 2 R(n)

or

R(n+1) = sqrt(R(n)) + 1

(Edit: that second function can only be used if R(n) is even, which would make R(n+1) odd; otherwise if R(n) were odd and R(n+1) were even then the OP would call for dividing R(n+1) by 2 instead of using the sqrt+1 formula and a sequence would not go from R(n+1) to R(n). R(n) will be even if the first function is applied, so this just means that the second function cannot be applied twice in a row. Later on in this argument, that will mean that some 2^a terms must have an exponent greater than zero.)

Simply by applying the first function many times, we can say that you can reach all numbers of the form

2^a

If you apply the first function many times, then apply the second function, then the first function many more times, you could say that you can reach all numbers of the form

[sqrt(2^a)+1] x 2^b

Since sqrt(2^a) is an integer if and only if a is even, you could rewrite that as

(2^a + 1) x 2^b

If you apply the second function to one of those numbers and then apply the first function some more, then you can reach all numbers of the form

(sqrt[(2^a + 1) x 2^b] + 1) x 2^c

Now things start getting useful. That square root must be an integer.

sqrt[(2^a + 1) x 2^b] = sqrt(2^a + 1) x sqrt(2^b)

Since a must be >0, the sqrt(2^a + 1) term will not have a factor of sqrt(2), therefore the whole expression will be an integer only if each of the two separate square roots on the right are integers. sqrt(2^b) is easy. For sqrt(2^a + 1) to be an integer, I suspect but cannot at this point prove that this is only true for a=3 (sqrt[2³+1]=3).

If that's the case, then you can reach numbers of the forms

2^a

(2^a + 1) x 2^b

(3 x 2^b + 1) x 2^c

Now if you were to use the R(n+1) = sqrt(R(n)) + 1 function yet again...

All numbers of the form [sqrt([3 x 2^b + 1] x 2^c) + 1] x 2^d can be reached.

Now for that sqrt to be an integer...

sqrt([3 x 2^b + 1] x 2^c)

we again really have to find numbers where the left term (3 x 2^b + 1) is a square. I again suspect but cannot prove that this is true only for b=3 (sqrt[3 x 2³ + 1]=5) and b=4 (sqrt[3 x 2⁴ + 1]=7). So we have numbers of the form

(5 x 2^c + 1) x 2^d

(7 x 2^c + 1) x 2^d

So total set of solutions so far is

2^a

(2^a + 1) x 2^b

(3 x 2^b + 1) x 2^c

(5 x 2^c + 1) x 2^d

(7 x 2^c + 1) x 2^d

Now I think you should be able to see where I'm going with this.

By the same logic, the only solution I can find for sqrt([5 x 2^c + 1] x 2^d) is c=4 (sqrt[5 x 2⁴ + 1]=9); and for sqrt([7 x 2^c + 1] x 2^d) is c=5 (sqrt[7 x 2⁵ + 1]=15.

So total set of solutions so far is

2^a

(2^a + 1) x 2^b

(3 x 2^b + 1) x 2^c

(5 x 2^c + 1) x 2^d

(7 x 2^c + 1) x 2^d

(9 x 2^d + 1) x 2^e

(15 x 2^d + 1) x 2^e

Now to consider the general case. Given an equation of the form

(n x 2^a + 1) = m²

If you're given a value for n I'd like to find some sort of way of finding values of m that satisfy this equation where {n, a, m} are integers, or at least put limits on what values m could be in relation to n such that you could show that, say,

(13 x 2^a + 1) x 2^b

will not appear on the list of solutions to produce a value of 27.

Edited March 8, 2014 by plasmid

[bonanova]

Recall the procedure O is to subtract 1, remove all 2 factors and then square.

Prove:

The sequence of numbers created by repeatedly applying O to 2^p - 1 reaches unity

First we show that another class of numbers, of the form (2^q - 1)², converges.

That is, that O (2^q - 1)² = (2^q-1 - 1)², so that eventually (2¹-1)² = 1 is reached

Expand: (2^q - 1)² = 2^2q - 2x2^q + 1

Subtract 1: 2^2q - 2x2^q = 2^q (2^q - 2) = 2x2^q (2^(q-1) - 1)

Remove factors of 2: (2^(q-1) - 1)

Square: (2^q-1 - 1)².

Also, a similar analysis shows that O (2^q + 1)² = (2^q-1 + 1)² eventually reaching (2¹ + 1)² = 2³ + 1, which is of the convergent form 2^p + 1.

Thus, numbers of the form (2^q + 1)² converge as well.

Now show that O (2^p - 1) = (2^q - 1)²

n = 2^p - 1

Subtract 1: 2^p - 2 = 2 (2^p-1 - 1)

Remove factors of 2: (2^p-1 - 1)

Square: (2^p-1 - 1)².

Our collection of proved convergent numbers now includes

(2^p - 1) = 1 3 7 15 31 63 127 255 511 1023 ...,

(2^p) = 2 4 8 16 32 64 128 256 512 1024 ... ,

(2^p + 1) = 3 5 9 17 33 65 129 257 513 1025 ...,

(2^p - 1)² = 1 9 49 225 961 3969 16129 65025 261121 1046529 ...,

(2^p + 1)²= 9 25 81 289 1089 4225 16641 66049 263169 1050625 ...,

and all 2^p multiples of them.

This list leaves out some small numbers that converge: 11, 13, 19, 21 and 23.

If we can find simple patterns for them, we might see why 27 diverges.

That is, it won't have a simple pattern.

[bonanova]

On a class of Collatz procedures.doc

[plasmid]

Interesting, but I'm not sure that those formulas cover all numbers that converge, so I don't think you could conclude that a number doesn't converge based on the fact that it doesn't fit any of the described cases that do converge. As an example, 23 converges but I don't think it fits any of those cases.

[plasmid]

The following perl program brute-forces an answer to my earlier question, which I think gives a solution, although I'd rather find a way to solve it without brute force.

This looks for all pairs of (n, m) such that n x 2

^a + 1 = m² in the range where n and m are less than 1000. Rearranging gives 2^a = (m² - 1) / n, so it looks for all cases where log base 2 of (m² - 1) / n is an integer greater than zero.

#!/usr/bin/perl
for($n=1; $n<1000; $n++){
  for($m=2; $m<1000; $m++){
    $result = log(($m*$m-1)/$n) / log(2);
    if( (int($result) == $result) && ($result > 0) ){
      print("n $n, m $m\n")
    }
  }
}

Combined with my approach earlier, the output lets you look for a number n and then see what values of m would produce a working answer for n x 2^a + 1 = m², which therefore tells you what values of n could appear in the next expression. Following this out gives these values for n with the associated new values of n that would be allowed by performing the sqrt(R(n))+1 function again:

1 -> 3

3 -> 5, 7

5 -> 9

7 -> 15

9 -> 17

15 -> 11, 31

17 -> 33

11 -> nothing

31 -> 63

33 -> 65

63 -> 127

65 -> 129

127 -> 255

129 -> 257

255 -> 511

A pattern appears to emerge. And 13 isn't on the list, so 27 could not be reached by starting at 1 and going through the collatz algorithm in reverse. I just don't have a good way of proving that these would definitely be the only solutions to n x 2^a + 1 = m²

[bonanova]

Odd numbers of the form

[1] n(p, q) = 1 + 2^p +/- 2^q, where p > q.

transform under O (subtract 1; remove all factors of 2; square) to odd squares of the form

[2] O n(p, q) = m²(p, q) = (2^p-q +/- 1)².

Squares of that form, (2ⁿ +/- 1)², transform under O into smaller squares of the same form:

[3] O (2ⁿ +/- 1)² = (2^n-1 +/- 1)²

Repeated applications of O eventually reach 1, and thus numbers obeying [1] converge.

All other (odd) squares transform into larger squares.

Yesterday I thought that was the solution, and since 27 had been found to be the smallest

divergent number, it had to be the smallest odd number that does not satisfy equation [1].

Then I met the number 23. It converges but does not satisfy [1].

Then I found 47. Same thing. It converges but does not satisfy [1].

Investigating this I found, also, that O produces squares that do not satisfy equation [3].

O (23) = 11².

O (47) = 23².

Neither of 11 and 23 differ by 1 from a power of 2.

But applying O a 2^nd time gives an OK result:

O (11²) = 15².

O (23²) = 33².

Both 15 and 33 do differ by 1 from a power of 2. So 23 and 47 are shown to be convergent under the above rules.

But why is that? Why is an extra O step needed for 23 and 47 (and other numbers?) to comply with [3]?

Well, for any number x,

[4] O (x 2^p + 1) = x².

And 23 = 11x2¹ + 1, and 47 = 23x2¹ + 1.

So the result produced by O is dictated by the ability to express 23 and 47 in that form.

That is, O must produce 11² = 121, and 23² = 529, respectively, for those numbers.

If we look at 121 and 529 as squares, we see them as mavericks by not satisfying [3].

But if we look at 121 and 529 as ordinary odd numbers, we see that they obey [1].

That is, even though 11² and 23² don't fit [3] as squares, they fit [1] as numbers:

121 = 1 + 2⁷ - 2³

529 = 1 + 2⁹ + 2⁴

So here is another class of convergent numbers: numbers that obey [1] by applying O to them.

This can happen whenever an odd square coincidentally has the form of equation [1].

In those cases, equation [4] discloses a family of numbers (with p as a parameter) that do not (necessarily) obey [1] but will still converge.

In those cases, O accomplishes [2] first, and thereafter accomplishes [3].

So here is the modified list of classes of convergent numbers.

1. Odd numbers of the form 1 + 2^p + 2^q or of the form 1 + 2^p - 2^q.
2. Odd numbers, e.g., 23, 45, 89 and 47, 93 ... that O transforms into that form.
3. Odd squares of the form (2^p + 1)² or of the form (2^p - 1)²
4. Even numbers formed by multiplying a convergent odd number by 2^p, and of course 2^p itself.

bonanova's conjecture: All other numbers, even or odd, diverge.

The smallest divergent number is 27.

The smallest even divergent number is 2x27 = 54.

I would be remiss if I did not thank phil1882 for a very interesting puzzle and for several sleepless nights.

plasmid, I went over my stuff tonight and found the number 23 also. That number, and 47 and a few others, converge for a simple reason explained in the spoiler, and I think that makes the list complete. However, I would love to learn of any other mavericks or, even more interestingly, any other generating equation.

[plasmid]

The thing I still don't understand is whether or not you can prove that you've got a set of generating functions that will cover all numbers that will converge. That's why I took the different approach of starting at the number 1 and applying the algorithm backwards -- if you can cover all cases that can be reached by working from 1 backwards then you know you've covered every number that converges, so any number not on that list can't converge. I just can't come up with an adequate way to show definitively that I've covered all generating functions of the form

(n x 2^a + 1) x 2^b

by finding all values of n using the function

sqrt(n x 2^a + 1) = next value of n

In fact I know I'm missing some numbers that do converge, maybe because the generating function behaves strangely at higher values or something, because my approach didn't pick up that 47, 93, and 185 converge using the list of numbers generated in the previous perl program. (Either that or maybe rounding errors are making my computer miss whether it's dealing with integers or not after taking log base 2.)

If you want to make a list of numbers that your functions cover, you could compare it to the list of the numbers from 1 to 200 that appear to diverge: 27, 39, 43, 51, 53, 55, 59, 71, 45, 77, 79, 83, 85, 87, 91, 95, 99, 101, 103, 105, 107, 109, 111, 115, 117, 119, 123, 135, 139, 141, 143, 147, 149, 151, 153, 155, 157, 159, 163, 165, 167, 169, 171, 173, 175, 179, 181, 183, 187, 189, 191, 195, 197, 199 and multiples of powers of two for each of those.

[bonanova]

I match your list of divergent numbers. I decided to increase the range to 1000.

Convergent numbers become the minority pretty quickly, so I tabulated

them, instead of the divergent numbers. There are 286.

Convergent numbers from 2 TO 1000

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 29 30 31
32 33 34 35 36 37 38 40 41 42 44 45 46 47 48 49 50 52 56 57 58 60 61 62
63 64 65 66 67 68 69 70 72 73 74 76 80 81 82 84 88 89 90 92 93 94 96 97
98 100 104 112 113 114 116 120 121 122 124 125 126 127 128 129 130 131
132 133 134 136 137 138 140 144 145 146 148 152 160 161 162 164 168 176
177 178 180 184 185 186 188 192 193 194 196 200 208 224 225 226 228 232
240 241 242 244 248 249 250 252 253 254 255 256 257 258 259 260 261 262
264 265 266 268 272 273 274 276 280 288 289 290 292 296 304 320 321 322
324 328 336 352 353 354 356 360 363 368 369 370 372 376 384 385 386 388
392 400 416 448 449 450 452 456 464 480 481 482 484 488 496 497 498 500
504 505 506 508 509 510 511 512 513 514 515 516 517 518 520 521 522 524
528 529 530 532 536 544 545 546 548 552 560 576 577 578 580 584 592 608
640 641 642 644 648 656 672 704 705 706 708 712 720 725 726 736 737 738
740 744 752 768 769 770 772 776 784 800 832 896 897 898 900 904 912 928
960 961 962 964 968 976 992 993 994 996 1000.

In this list there are three numbers that I did not find using my current method.

The numbers are 363, 725 and 726 (which is 2x363.)

363 and 725 converge, following the squares of : 181 4095 2047 1023 511 255 127 63 31 15 7 3 1.

181² = 32761 = 1 + 32768 - 8 which is canonical form.

That uncovers a third set of anomalous convergent numbers. They are:

11x11 = 121 = 1 + 128 - 8. Spawns 23 45 89 177 353 705 1049 2817 5633 ...
23x23 = 529 = 1 + 512 - 16. Spawns 47 93 185 369 737 1473 2945 5889 ...
181x181 = 32761 = 1 + 32768 - 8. Spawns 363 725 1449 2897 5793 ...

and their powers-of-2 multiples, like 726 above.

I'm more firmly convinced this is a complete set of convergent numbers.

Convergent numbers get increasingly sparse in the high-number range.

The anomalous ones are an increasingly sparse subset: 11 - 23 - 181 - ?

The only other type anomaly I can imagine is one where O must be

applied twice (or more) to get to canonical form.

It would be interesting to write a program to find all the odd squares that

have canonical form, and the numbers they spawn. I don't think there are many.

OK that was a dumb statement. They are probably infinite. But very sparse.

I agree that none of this is a proof.

[plasmid]

I went back and noticed that my approach didn't miss 47, 93, and 185 -- I just missed transcribing that (33 x 2^a + 1) has 529 (m=23) as a solution, so 23 should have been included on my list and 23 x 2² + 1 = 47, 23 x 2³ + 1 = 93, and 23 x 2⁴ + 1 = 185. So all's well there.

At first I thought my algorithm was also going to miss 363 because solving (n x 2^a + 1) = 363 would mean 181 must be on the list, and it initially looked like it wasn't because values for n were growing past 181 and looked like they had settled into a pattern. But there was a break in the pattern when I started looking at larger values for n and m. The set of n's and what m's they would produce goes

1 -> 3

3 -> 5, 7

5 -> 9

7 -> 15

9 -> 17

15 -> 11, 31

17 -> 33

11 -> nothing

31 -> 63

33 -> 23

33 -> 65

63 -> 127

23 -> nothing

65 -> 129

127 -> 255

129 -> 257

255 -> 511

257 -> 513

511 -> 1023

513 -> 1025

1023 -> 2047

1025 -> 2049

2047 -> 4095

2049 -> 4097

4095 -> 181

4095 -> 8191

Incidentally, 181 also -> nothing

I have not yet had a chance to think through why my algorithm is generating n's that don't follow the pattern of being 2^a +/- 1 for exactly the same set of numbers that you consider anomalous, and I will not have such a chance before going to sleep, but it seems unlikely to be coincidence.

[bonanova]

I think we both have the entire playing field covered.

My view of the field includes "canonical" numbers generated from p and q.

It also includes "anomalous" numbers that arise from non-canonical roots

(11, 23, 181,...) whose squares (121, 529, 32761, ...) are canonical.

The convergent roots each spawn an infinite family of other convergent

numbers.

I've been working from a sketch of the field, below, that shows "anomalous"

numbers and the recursion formula in red. The sketch shows how and where

they branch into the canonical field.

The anomalous numbers seem to attach to alternating branches and with

alternating parity of powers of 2. That may be a coincidence, but I think it

would be interesting to find the next odd square that has canonical form.

Can you think of other places to search?

[plasmid]

Solutions to the equation n x 2^a + 1 = m² using the notation I've been working with should give you all anomalous numbers if you can solve it... or to be precise: if you can come up with a way of recursively coming up with all solutions for m given a set of n's, and then adding those m's to the list of n's and coming up with more m's, etc.

In my lists of pairs of integers (n, m) that satisfy that formula, I noticed that all numbers of the form 2^b-1 and 2^b+1 were solutions. Now that I know my solutions have that form, I can prove that all numbers of those forms are solutions using my approach, which makes our approaches in practice look much more similar.

If n is of the form 2

^b-1 then setting a equal to b+2 gives

n x 2^a + 1

(2^b-1) x 2^b+2 + 1

2^2b+2 - 2^b+2 + 1

2^2x(b+1) - 2 x 2^b+1 + 1

(2^b+1 - 1)²

m = 2^b+1 - 1

If n is of the form 2^b+1 then setting a equal to b+2 gives

n x 2^a + 1

(2^b+1) x 2^b+2 + 1

2^2b+2 + 2^b+2 + 1

2^2x(b+1) + 2 x 2^b+1 + 1

(2^b+1 + 1)²

m = 2^b+1 + 1

By modifying my perl code a bit I made it much more efficient and have it outputting only m's that have a preceding n in the solution set, so it can look for anomalous numbers more efficiently with output that's easier to digest.

#!/usr/bin/perl
use warnings;

@solutions = (1);
@workingset = (1);
while (@workingset) {
  $n = shift(@workingset);
  for($a=1; $a<50; $a++) {
    $m = ($n * (2**$a) + 1)**0.5;
    if( (int($m) == $m) && ($m/2 > int($m/2)) ) {
      print("n $n, m $m, a $a\n");
      push(@solutions, $m);
      push(@workingset, $m);
    }
  }
}
print "Solution set: @solutions";

In case you're wondering, that && ($m/2 > int($m/2)) bit is just to weed out even values of $m that sometimes arise from rounding error -- an even m should not be a solution since m² = n * 2^a + 1.

The only anomalous numbers on the list it creates are the same ones you have

11 (arising from n=15 (2⁴-1), a=3)

23 (arising from n=33 (2⁵+1), a=4)

181 (arising from n=4095 (2¹²-1), a=3)

And it searches up to about 10¹⁴ (about 2⁴⁷) so it's maybe covering them all. If I try increasing the upper limit on the exponent $a, then it starts spitting out numbers that arise from rounding error (confirmed to just be rounding error by a separate program).

But I cannot prove that those are the only anomalous solutions.

Edited March 15, 2014 by plasmid

[bonanova]

I searched up to 10²⁰and didn't find any more anomalous instances.

I think we should share the Nobel Prize for this one....

Edited March 17, 2014 by bonanova
Comment