VLRPNs

[ThunderDawg]

I clearly meant 1k x 1k >.<


I am going to spend some time using Cornell's arXiv,
before my crackpot rating goes through the roof.


thanks for all your help. /thread

[CRGreathouse]

Originally Posted by ThunderDawg

I clearly meant 1k x 1k >.<

I actually thought you intended 1M x 1M...

A 1k x 1k image is still fairly impressive. It could encode (in monochrome) a prime around 300th place in Chris Caldwell's list.

I'd still like to see one of the primes you've generated, if not the method. Good luck with the arXiv.

[flouran]

Originally Posted by ThunderDawg

I clearly meant 1k x 1k >.<


I am going to spend some time using Cornell's arXiv,
before my crackpot rating goes through the roof.


thanks for all your help. /thread

Ummm....you realize you need to be endorsed to publish on the arXiv right?
And ummmm....in order to be endorsed your manuscript MUST be mathematically coherent.

Just keep that in mind.

[ThunderDawg]

Thanks.

I am going to try to lower my crackpot rating by being less paranoid. I think I might be able to explain it in less than 5,000 words.



I used to play math challenges at curiousmath and this is one that I won. Google "One Million Light Bulbs", but for some reason, it takes you to page 2 :-\

Whatever. It went thusly:

Picture this, you have an array of 1,000,000 light bulbs, numbered 1 to 1,000,000, all of which are off (and all of which work).

The following task involves these light bulbs and an action we'll call "flipping". Flipping simply means changing the state of a light bulb. If the bulb is off, flipping will turn it on. If the bulb is on, flipping it will turn it off.
Starting with all the light bulbs off, you start at bulb #1, and flip the state of every bulb. Once you've done that, you go back and start with bulb #2, flipping the state of every second bulb. Next, you go back, start with bulb #3, and flip the state of every third bulb.

This continues all the way up to 1,000,000, where you flip the state of every "millionth" bulb (obviously, just the one bulb).

Here's the question: After performing this massive task, which light bulbs will be on, and which light bulbs will be off?

I think I used a Perl script to I solve it, but I also wanted to come up with a manual method of solving it, and I created a spreadsheet that calculated each value for a 100 x 100 array. The 1k x 1k calculations weren't even necessary. I could just continue the trend that showed itself.

Then I noticed something unusual: the "On" bulbs were pointing to Primes, not just one or two, but all of them (it was very difficult to not say that in allcaps, so I hope I get at least one point reduction in my crackpot score).

If you wish to recreate the 100 x 100 spreadsheet, use Number formatting with red positive numbers, make the -0-s invisible, 0 decimals and shrink the columns down as far as you can. Zoom to 25% or lower. I used formulae to calculate ever "On" and "Off" - you'll have to do that yourself.

If you are a True Prime Nerd, you will see it. Wallá.

This I did with only the 100 x 100 matrix. The 1000 x 1000 no longer needs calculations. You can just repeat the trend going on. This is also true for 1m x 1m, etcetera. I hope you have scrollbars. I have checked all Primes under 1 million and spot checked many under one billion. I still haven't made the leap to a billion digits, but it's not far off, imho. I was wrong earlier, I haven't worked on this for 3 years, it's closer to four.

[ThunderDawg]

Wait. No. Make only Prime Numbers red. I only did this as a lark.

But you can't miss it. They form a pattern among the "On" Bulbs.

[CRGreathouse]

Originally Posted by flouran

And ummmm....in order to be endorsed your manuscript MUST be mathematically coherent.

If only that were true.

Originally Posted by ThunderDawg

If you wish to recreate the 100 x 100 spreadsheet, use Number formatting with red positive numbers, make the -0-s invisible, 0 decimals and shrink the columns down as far as you can. Zoom to 25% or lower. I used formulae to calculate ever "On" and "Off" - you'll have to do that yourself.

Well, what you've developed is correct. More specifically, it's a sieve that can discover the primes below n in time roughly n log n log log n. It's an excellent method, essentially the same as that developed by Eratosthenes. Modern improvements to the sieve (using the theory of binary quadratic forms) can make it run in sublinear time.

[ThunderDawg]

If you look at the "sidewalk", to the right each (red) Prime occurs at every stop sign. Right of that, no Primes exist.

To the left, they follow a straight line. Left of those is more jumbled, but all other (red) primes are there. The time I have spent was mostly figuring out how to predict those irregular looking ones. But they are All "On".

http://i48.tinypic.com/2ij2j46.jpg

[ThunderDawg]

Originally Posted by CRGreathouse

Well, what you've developed is correct. More specifically, it's a sieve that can discover the primes below n in time roughly n log n log log n. It's an excellent method, essentially the same as that developed by Eratosthenes. Modern improvements to the sieve (using the theory of binary quadratic forms) can make it run in sublinear time.

Well, that answers the OPQ, or at least narrows down my search.

Thanks for your time.

[Mini-Geek]

The challenge calls for flipping beginning on every bulb. This is not a prime sieve, and as far as I can tell it's not how you've interpreted it. How did you interpret it? The question could be modified to be the Sieve of Eratosthenes, but as it is this is not one. Here's what that sieve would look like, phrased like the original question:

Picture this, you have an array of 1,000,000 light bulbs, numbered 1 to 1,000,000, all of which are on.

First, turn off bulb #1, since 1 isn't considered a prime. Then, you start at bulb #2, and turn off every second bulb after bulb #2. Once you've done that, you go back and start with the next bulb that's on, bulb #3, and turn off every third bulb after bulb #3. Next, you'll see that bulb #4 is off, skip it, see that bulb #5 is on, and turn off #10, #15, ...

Continue up to bulb #1,000,000.

Here's the question: After performing this massive task, which light bulbs will be on, and which light bulbs will be off?

This only has to continue up to bulb #1000, (the square root of 1,000,000) because every composite less than or equal to 1,000,000 must have at least one multiple less than or equal to 1,000.
The prime number's lights will be on, and only the prime number's lights.
Note that this works, and has been known for a very long time, but is only useful for generating large lists of relatively small primes, not for generating very large primes, and that more efficient (and more complex) algorithms are known, like the Sieve of Atkin.

Now back to the original problem:
The problem ends with all lights corresponding to square numbers on, and all other lights off.
Why? Each number starts with its light off, and changes each time you reach a divisor of the number (including one and the number itself), so if there is an odd number of divisors, the light will flip an odd number of times and end in the on position. If there is an even number of divisors, the light will flip an even number of times and end in the off position.
Now the question is: what numbers have an odd number of divisors? Square numbers are the only numbers with an odd number of divisors.
To see why this is, look at a listing of the divisors of a number, like 36 (a square number): 1, 2, 3, 4, 6, 9, 12, 18, and 36. Notice how each divisor is paired with another, like 1 and 36 (36=1*36) or 9 and 4 (36=4*9), except for 6, which is paired with itself (36=6*6). Only squares have such an unpaired divisor, so only they have an odd number of divisors, so only they have their lights left on.

I worked this manually up to 20:

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 - the numbers
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 - starting state
1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 - flipping starting at 1
1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0 - flipping starting at 2
1  0  0  0  1  1  1  0  0  0  1  1  1  0  0  0  1  1  1  0 - and so on...
1  0  0  1  1  1  1  1  0  0  1  0  1  0  0  1  1  1  1  1
1  0  0  1  0  1  1  1  0  1  1  0  1  0  1  1  1  1  1  0
1  0  0  1  0  0  1  1  0  1  1  1  1  0  1  1  1  0  1  0
1  0  0  1  0  0  0  1  0  1  1  1  1  1  1  1  1  0  1  0
1  0  0  1  0  0  0  0  0  1  1  1  1  1  1  0  1  0  1  0
1  0  0  1  0  0  0  0  1  1  1  1  1  1  1  0  1  1  1  0
1  0  0  1  0  0  0  0  1  0  1  1  1  1  1  0  1  1  1  1
1  0  0  1  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0 - flipping starting at 11 through 20

(1 means on, 0 means off)
Note the ones that are on: 1, 4, 9, 16. Notice anything about those?
Since the interest is on primes, I'll point out the unique thing about them: they only switch twice, once on (at 1) and once off (at the number itself). This is a direct consequence of what I mentioned above: each number/bulb is flipped on each divisor. Since the only divisors a prime has is, by definition, one and itself, it only flips twice.

[cheesehead]

Originally Posted by ThunderDawg

The result depends crucially on the exact meaning of "start with bulb #N, and flip the state of every Nth bulb".

However, the following example seems to clarify that:

This continues all the way up to 1,000,000, where you flip the state of every "millionth" bulb (obviously, just the one bulb)

So, bulb #N is to be flipped, as well as every Nth bulb after bulb #N.

As Mini-Geek points out, the array wins up with only the squares ON, and two rule changes are necessary to change the algorithm to a prime-finder.

Suppose we make just one of those rule changes. What do we get?

If we change only the rule that when we start at bulb #N, then bulb #N itself is flipped, (i.e., changed to not flipping bulb #N, but flip every Nth bulb after bulb #N) we get:

1 OFF
2 ON
3 ON
4 OFF
5 ON
6 ON
7 ON
8 ON
9 OFF
10 ON

All the squares wind up OFF, all nonsquares ON. (A sieve for nonsquares :-)

If we change only the rule that any bulb can be flipped, regardless of whether it's ON -- to -- flip a bulb only if it's ON, we get:

1 OFF 
2  OFF
3  OFF
4  OFF

. . .

All bulbs stay OFF!

If we change only the rule that any bulb can be flipped, regardless of whether it's ON -- to -- flip a bulb only if it's OFF, we get:

1 ON
2 ON
3 ON
4 ON

. . .

All bulbs stay ON once they've been flipped ON, which occurs during the first pass.

Not too interesting in the latter two cases.

[ThunderDawg]

It is not really comparable to Eratosthenes. He used a very elementary process of elimination. I have completely skipped that process. Granted, I checked them against known primes that were discovered thousands of years ago. If mine is an extension of that sieve, then I haven't wasted all this time.

But there is the little matter of getting past those relatively tiny numbers.

If my model can predict their location, the problem is finding really large ones in an image too large to load or view. But since the pattern is known, maybe I can develop a peephole where these enormous images are no longer necessary. Just like a telescope views faraway galaxies. I know, my crackpot rating just shot up again. But, think about it, we don't see planets in faraway star systems, we can only see the wobble of the star's light. Yeccchhh. Bad analogy.