Saturday, October 6, 2012

A Proth Number is Always Odd?

The short answer is "Yes, I think so."

The long answer is "Probably, and here's why." A Proth number is any positive integer of the form k * 2^n + 1 where k is any positive, odd integer and n is a positive integer such that 2^n > k.

The example I like to use is 3 * 2^2 + 1. 3 x 4 = 12 + 1 = 13. 13 is therefore the smallest possible Proth number, and is also a prime. The next few are 25, 49, and 97, all of which are odd. 97 is also prime.

The fact is, all powers of 2 are even numbers, and any even number multiplied by any other positive integer is also even. For these purposes, an "even number" is any positive integer which is divisible by 2 with a remainder of exactly 0 - these are concepts of discrete math that any elementary school student knows!

This means that if you add 1 to any even number, the sum is always odd. Thus, a Proth number is always odd.

This begs the question - why does GJSieve need three separate threads to test numbers?

Thread 1 starts at x = 2 and divides the Proth number each time by x += 3 (that is, x increments by 3 each time). Thread 2 starts at x = 3 and thread 3 at x = 4. All of these threads will test even numbers, but they don't necessarily have to at all.

An odd number cannot be divisible by an even number - can it?

This time, the short answer is "No." An even number multiplied by any other number results in another even number. The product is always even. Divisibility is simply finding the other multiplier when you know one number and the product.

It would be difficult to make GJSieve test only odd numbers, though. It would actually take a lot longer. This would involve a thread starting at 3 and incrementing by 2 each time. Alternatively, we could use 2 threads, starting at 3 and 5 and incrementing by four each time. We could use 3 threads, starting at 3, 5, and 9 and incrementing by four each time - or six? - no wait, then we'd test the same number twice. Or more.

What a dilemma!

See, I'm trying to develop a new testing method I can call my own, but currently it's just brute-force trial division in a fancy threaded fashion. Not particularly insightful or efficient in terms of time or computing power!

I'll do more on this later, I'm sure...

No comments:

Post a Comment