mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2007-05-17, 23:44   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

3×17×83 Posts
Default 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.
davar55 is offline   Reply With Quote
Old 2009-08-23, 21:01   #2
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

17·79 Posts
Default

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
lavalamp is offline   Reply With Quote
Old 2009-08-23, 21:31   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2009-08-23, 21:49   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

143608 Posts
Default

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?
fivemack is offline   Reply With Quote
Old 2009-08-24, 07:54   #5
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

68616 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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
S485122 is offline   Reply With Quote
Old 2009-08-24, 09:52   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-08-24, 10:06   #7
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

17·79 Posts
Default

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
File Type: zip unpossible.zip (712 Bytes, 130 views)
lavalamp is offline   Reply With Quote
Old 2009-08-24, 11:18   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26748 Posts
Default

Quote:
Originally Posted by fivemack View Post
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)))
R. Gerbicz is offline   Reply With Quote
Old 2009-08-24, 11:40   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by lavalamp View Post

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].
R.D. Silverman is offline   Reply With Quote
Old 2009-08-27, 15:23   #10
davar55
 
davar55's Avatar
 
May 2004
New York City

3×17×83 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
davar55 is offline   Reply With Quote
Old 2009-08-27, 17:03   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Need help finding the pattern... WraithX Other Mathematical Topics 17 2017-01-10 19:57
Prime Number Pattern, Probably not but have a look please. matthewsx7 Miscellaneous Math 21 2016-06-25 08:30
Prime pattern thoughts jasong jasong 11 2013-02-13 01:36
Initial Pattern davar55 Puzzles 6 2007-06-12 00:00
My computer distrupts my sleeping pattern 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.