mersenneforum.org A Pattern That Is Not
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-17, 23:44 #1 davar55     May 2004 New York City 3×17×83 Posts A Pattern That Is Not The Law of Small Numbers strikes again ! I was looking for something new in the primes, and thought I had come across a new pattern. I got myself into a lot of trouble here in the forum when I extrapolated a pattern I thought I had found in the Mersenne primes, so I knew I had to be more careful with this "new" pattern. The sequence of Number of Primes < 10n begins: 4,25,168,1229,9592,78498,664579,5761455,50847534,... But 4 and 25 are perfect squares. There "must" be a pattern. And 168 = 13^2 - 1 is nearly a square, and the correction factor 1 is. And 1229 = 35^2 + 4 is nearly a square, and 4 is. Maybe there's a first or second order pattern ... Well, 9592 = 98^2 - 12 already starts the drift away from such a pattern. And 78498 = 280^2 + 98 isn't so close to a square, although 98 is close. Maybe there's a third order pattern ... But 664579 = 815^2 + 354, and 354 = 19^2 - 7 is also "drifting" from being nearly a square. You can see where this went. In short, by the ninth term (sooner if you disagree with what constitutes being "close" to a square), no obvious square pattern persists. Although there might be a fourth order pattern ... Lesson learned. New mathematical patterns and properties are not so easy to come by.
 2009-08-23, 21:01 #2 lavalamp     Oct 2007 Manchester, UK 17·79 Posts I know this thread is a bit old but it interested me so I'm reviving it. All odd numbers can be generated if you allow subtraction of squares, for example: 1229 = 615^2 - 614^2 664579 = 332290^2 - 332289^2 Additionally, all multiples of 4 can be generated by subtracting odd next door neighbours, for example: 168 = 43^2 - 41^2 9592 = 2399^2 - 2397^2 Some numbers can't be made using subtraction or addition with only two squares, such as 6 and 50847534. Other numbers like 78498 can though: 78498 = 63^2 + 273^2
2009-08-23, 21:31   #3
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by lavalamp Some numbers can't be made using subtraction or addition with only two squares, such as 6 and 50847534. Other numbers like 78498 can though: 78498 = 63^2 + 273^2
Yes. Those numbers that can are of 0 density, though only very slightly -- they're more common than primes, for example.

 2009-08-23, 21:49 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 143608 Posts Ooh, that's a nice result; do you happen to know what the asymptotic form of N(sum of two squares less than X) is?
2009-08-24, 07:54   #5
S485122

Sep 2006
Brussels, Belgium

68616 Posts

Quote:
 Originally Posted by lavalamp Additionally, all multiples of 4 can be generated by subtracting odd next door neighbours, for example: 168 = 43^2 - 41^2 9592 = 2399^2 - 2397^2
You probably mean "all multiples of 8 can be generated by subtracting the square of consecutive odd numbersâ€ť.
(2n+1)2-(2n-1)2=8n
Both your examples are multiples of 8.

Jacob

2009-08-24, 09:52   #6
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by fivemack Ooh, that's a nice result; do you happen to know what the asymptotic form of N(sum of two squares less than X) is?
Yes, I do. It is a well known problem and can be found on the web.
A positive integer is the sum of two squares iff all of its prime factors
that are congruent to 3 mod 4 appear to an even power. i.e. If N
is divisible by a prime p that is 3 mod 4, then it must be divisible by p^(2k)
for some positive integer k.

2009-08-24, 10:06   #7
lavalamp

Oct 2007
Manchester, UK

17·79 Posts

Ah yes, it is multiple of 8 for odd numbers, but I didn't mean odd numbers, I meant next door but one neighbors. Not sure why I said odd, let's put that down to a misfiring neuron.

4 = 4 - 0
8 = 9 - 1
12 = 16 - 4
16 = 25 - 9
20 = 36 - 16

(n+1)^2 - (n-1)^2 = 4n

Using only addition of squares, any number that is 3 mod 4 cannot be made. I've attached a list of more that cannot be made, and also an explicit list of all integers less than 100 that cannot be made (there are 57, for less than 10^3 there are 670, 10^4 : 7,251, 10^5 : 75,972, 10^6 : 783,659).
Attached Files
 unpossible.zip (712 Bytes, 130 views)

2009-08-24, 11:18   #8
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

26748 Posts

Quote:
 Originally Posted by fivemack Ooh, that's a nice result; do you happen to know what the asymptotic form of N(sum of two squares less than X) is?
O(x/sqrt(log(x)))

2009-08-24, 11:40   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by lavalamp Using only addition of squares, any number that is 3 mod 4 cannot be made. I've attached a list of more that cannot be made.
I will assume that by "addition of squares", you do not mean what you write.
Every positive integer is the sum of at most 4 squares. I will assume that
what you do mean is: "sum of TWO squares". In mathematics, one needs
to be precise.

Further: Doesn't anyone read what I write? I completely characterized
the integers that are the sum of two squares in my prior post.

BTW, the proof is easy. I will offer a hint: The Gaussian integers are
a unique factorization domain. [UFD].

2009-08-27, 15:23   #10
davar55

May 2004
New York City

3×17×83 Posts

Quote:
 Originally Posted by R.D. Silverman I will assume that by "addition of squares", you do not mean what you write. Every positive integer is the sum of at most 4 squares. I will assume that what you do mean is: "sum of TWO squares". In mathematics, one needs to be precise. Further: Doesn't anyone read what I write? I completely characterized the integers that are the sum of two squares in my prior post. BTW, the proof is easy. I will offer a hint: The Gaussian integers are a unique factorization domain. [UFD].
Yes, this is a famous result, and thanks for providing only a hint,
as a good teacher would.

But can you tell us if this sheds any light on the original post
on a supposed pattern among the primes?

2009-08-27, 17:03   #11
CRGreathouse

Aug 2006

32·5·7·19 Posts

Quote:
 Originally Posted by davar55 But can you tell us if this sheds any light on the original post on a supposed pattern among the primes?
I don't think there's anything to say here. You noticed that the first two terms, 4 and 25, were squares, so you test the text (say) ten terms. You find that zero are squares; the expected count is 0.1298, so that's a reasonable result. You notice that the next two are within a square distance of a square, so you test the next ten. You find that zero are a square distance from the closest square; the expected count is something like 0.53, still quite reasonable.

So the numbers seem to act pretty much like you'd expect random numbers to act. If someone wants to fix my expected count for the second-order sequence and calculate one for the third-order, be my guest; it's a little hairy for me to do at the moment. But I'd be surprised if there was a significant deviation from the expected value.

 Similar Threads Thread Thread Starter Forum Replies Last Post WraithX Other Mathematical Topics 17 2017-01-10 19:57 matthewsx7 Miscellaneous Math 21 2016-06-25 08:30 jasong jasong 11 2013-02-13 01:36 davar55 Puzzles 6 2007-06-12 00:00 Vijay Lounge 6 2005-04-07 04:54

All times are UTC. The time now is 02:03.

Tue May 18 02:03:52 UTC 2021 up 39 days, 20:44, 0 users, load averages: 2.14, 1.95, 1.98