Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * - 1 votes

collatz sequence^2


  • Please log in to reply
15 replies to this topic

#11 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1449 posts
  • Gender:Male

Posted 13 March 2014 - 04:17 PM

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 2a + 1) x 2b
by finding all values of n using the function
sqrt(n x 2a + 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.
  • -1

#12 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5895 posts
  • Gender:Male
  • Location:New York

Posted 13 March 2014 - 11:01 PM

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.

 

1812 = 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.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#13 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1449 posts
  • Gender:Male

Posted 14 March 2014 - 06:18 AM

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

At first I thought my algorithm was also going to miss 363 because solving (n x 2a + 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 2a +/- 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.
  • 0

#14 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5895 posts
  • Gender:Male
  • Location:New York

Posted 15 March 2014 - 02:17 PM

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?

phil_numbers_half.jpg


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#15 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1449 posts
  • Gender:Male

Posted 15 March 2014 - 05:43 PM

Solutions to the equation n x 2a + 1 = m2 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 2b-1 and 2b+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.

Spoiler for proof of those


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.

Spoiler for modified perl code


The only anomalous numbers on the list it creates are the same ones you have
11 (arising from n=15 (24-1), a=3)
23 (arising from n=33 (25+1), a=4)
181 (arising from n=4095 (212-1), a=3)
And it searches up to about 1014 (about 247) 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 by plasmid, 15 March 2014 - 06:14 PM.

  • 0

#16 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5895 posts
  • Gender:Male
  • Location:New York

Posted 16 March 2014 - 08:04 AM

I searched up to 1020and didn't find any more anomalous instances.

 

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


Edited by bonanova, 17 March 2014 - 02:06 AM.
Comment

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users