Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2005-12-22 04:22:54

seerj
Member

Offline

Very interesting problems..

Hi all i'm new in this forum! [ And Happy Xmas Holidays!]
I should solve a problem and I think that it's not so difficult but I don't know where starts.
The problem is:
For which integer n >1 it is possible to arrange all the entire numbers from 1 to n around a circle so that the sum of two consecutive numbers is always a perfect square?
[and..]
Which is the smallest integer n>1 for which it is possible to find this circular sequence?

Thanks 2 all in advance!!

SeerJ

#2 2005-12-24 00:47:32

seerj
Member

Offline

Re: Very interesting problems..

Please...help me! tongue

Waiting for ur help

Happy Holidays

#3 2005-12-24 03:50:04

Ricky
Moderator

Offline

Re: Very interesting problems..

I made program to try to solve it with brute force, but for even a list of size 20, it needs to build and test at least 10^20 different lists, since the function is O(n!).

It should hopefully be finished by tonight, I'll let you know if I get anything.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#4 2005-12-24 05:48:53

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

what means that the sum is perfect square?


IPBLE:  Increasing Performance By Lowering Expectations.

#5 2005-12-24 05:52:58

Ricky
Moderator

Offline

Re: Very interesting problems..

√2, not perfect, not an integer.  Heck, not even rational.
√9 = 3, perfect square


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#6 2005-12-24 06:21:23

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

Here are some analisys that may be helpful:
We have n numbers between 1 and n. Their sum is n(n+1)/2.
Every two consecutive numbers make a perfect square. The sum of all perfect squares is 2n(n+1)/2=n(n+1)
so n(n+1) must be sum of n squares greater than 1.


IPBLE:  Increasing Performance By Lowering Expectations.

#7 2005-12-24 06:40:49

Ricky
Moderator

Offline

Re: Very interesting problems..

"The sum of all perfect squares is 2n(n+1)/2"

What exactly do you mean by the sum of all perfect squares?  That would be infinity.

Edit:

My program has ruled out all numbers up to a list of size 13.  Of course, with each size increase, the time it takes goes up by a factorial, so I fear it won't finish 20 by tonight.  We'll see.

Last edited by Ricky (2005-12-24 06:42:26)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#8 2005-12-24 06:42:19

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

The the remainder of the sum of every two consecutive numbers when it's divided by 4 must be 0 or 1.


IPBLE:  Increasing Performance By Lowering Expectations.

#9 2005-12-24 06:45:38

Ricky
Moderator

Offline

Re: Very interesting problems..

krassi_holmz wrote:

The the remainder of the sum of every two consecutive numbers when it's divided by 4 must be 0 or 1.

They don't have to be consecutive.  You can arrange them in any order you want around a circle, and every two numbers that are next to each other have to add up to a perfect square.

I prefer to see it as a list, then just add the first and last elements.  That's essentially what a circle is.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#10 2005-12-24 06:51:07

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

And for the Ricky's suggest that √2 is not even rational. Here's interesting theorem:

Let Q is the multitude of all numbers of the type a/b , a,b ∈ N (naturals)
Let R is the multitude of all numbers of the type a√b (b^(1/a)) , a,b ∈ N (naturals)
Then Q && R = N.
That means that every a√b that is not natural is not rational and every a/b that is not natural is not a root of an integer number.


IPBLE:  Increasing Performance By Lowering Expectations.

#11 2005-12-24 09:43:48

Ricky
Moderator

Offline

Re: Very interesting problems..

Then Q && R = N.

How exactly would you say "&&"?


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#12 2005-12-24 10:07:43

seerj
Member

Offline

Re: Very interesting problems..

&& stands for the logic AND

For example a right circular sequence could be this:


1 15 10 6 3          1+15=16 perfect square    15+10=25 perfect square ...till 3 +1 (the first number) is a perfect square
I was also lookin for a program in whatever language..

#13 2005-12-24 10:10:10

seerj
Member

Offline

Re: Very interesting problems..

I read another info. This integer n>1  is less than 50!! mh...
so  n is        1<n<50.. Now the problem is to look for the exact value!

#14 2005-12-24 10:29:04

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

So somebody could write a program.
The number of combinations between n numbers in circular table is exactly (n-1)!/2
if n = 50 this makes exactly 304140932017133780436126081660647688443776415689605120000000000 combinations. If there isn't any mathematical way the hard computation will be very hard.


IPBLE:  Increasing Performance By Lowering Expectations.

#15 2005-12-24 10:36:17

Ricky
Moderator

Offline

Re: Very interesting problems..

&& stands for the logic AND

It sure does, at least in computer science.  But now apply that to:

Then Q && R = N

It doesn't make sense.

Does it mean intersection?

For example a right circular sequence could be this:
1 15 10 6 3

Hold on.  You said in your first post:

all the entire numbers from 1 to n

Doesn't that mean that 2, 4, 5, 7... 14 would also have to be in there?

Last edited by Ricky (2005-12-24 10:38:02)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#16 2005-12-24 10:41:02

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

Here is ss with 7 numbers:
1 8 17 19 6 10 15


IPBLE:  Increasing Performance By Lowering Expectations.

#17 2005-12-24 10:46:01

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

And here's ss with 13 numbers:
1 24 12 4 5 11 14 2 7 9 27 22 3!


IPBLE:  Increasing Performance By Lowering Expectations.

#18 2005-12-24 11:05:44

Ricky
Moderator

Offline

Re: Very interesting problems..

I modified my program so that it selects from a list of integers from 1 to 100 and creates lists:

Edit: I realized my old program was producing duplicate results, for example:

2 34 47
2 47 34

So I made it eliminate (actually, not even check) these.

Size 3:

2 23 98
2 34 47
3 22 78
4 21 60
5 20 44
6 19 30
6 75 94
10 54 90
12 52 69
14 35 86
15 34 66
16 33 48
26 74 95
29 52 92
30 51 70
48 73 96

Size 4:
1 3 22 99
1 3 33 48
1 3 97 99
1 8 41 80
1 24 97 99
2 7 42 79
3 6 43 78
4 5 44 77

It's currently running, but takes quite a while.  I'll update posts with results as I get them.

Last edited by Ricky (2005-12-24 11:22:49)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#19 2005-12-24 11:10:03

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

Here's an algoritm that creates infinite series:
1.a1=1
Do
I is the smallest suqare that is greater than ai
if (I-ai) is unequal to all the numbers a1,a2, ... a3 then a(i+1) = (I-ai)
Next

That's how I created the upper sequenses.
I'll be glad if somebody test my algoritm. I think it will be one of the minimals.

Last edited by krassi_holmz (2005-12-24 11:16:44)


IPBLE:  Increasing Performance By Lowering Expectations.

#20 2005-12-24 11:15:29

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

I've loved this sequence!
I'm starting with making programs tommorow morning, because it's too late now.
See you!
wink


IPBLE:  Increasing Performance By Lowering Expectations.

#21 2005-12-24 11:18:52

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

Great, Ricky, but you don't have to compute all the numbers between 1 and 100.
Between 1 and n is enough. I think that will accelerate the algoritm.


IPBLE:  Increasing Performance By Lowering Expectations.

#22 2005-12-24 11:23:45

seerj
Member

Offline

Re: Very interesting problems..

krassi_holmz wrote:

And here's ss with 13 numbers:
1 24 12 4 5 11 14 2 7 9 27 22 3!

Yes! Right!! That way!
This problem is very nice but it's not easy neutral


However thanx to all!!!!

#23 2005-12-24 11:24:12

Ricky
Moderator

Offline

Re: Very interesting problems..

I'm still not sure what n is...  At first I thought it was the size of the list (circle), but that can't be right.  Could you please clarify this?


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#24 2005-12-24 11:31:07

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

I can't wait until tomorrow. n<>5 I wrote fast vb6.0 program:
Private Sub Command1_Click()
Const n = 5
For i1 = 1 To 5
For i2 = 1 To 5
For i3 = 1 To 5
For i4 = 1 To 5
For i5 = 1 To 5
If i1 <> i2 And i1 <> i3 And i1 <> i4 And i1 <> i5 And i2 <> i3 And i2 <> i4 And i2 <> i5 And i3 <> i4 And i3 <> i5 And i4 <> i5 And Squ(i1 + i2) + Squ(i2 + i3) + Squ(i3 + i4) + Squ(i4 + i5) + Squ(i5 + i1) = 5 Then Form1.Text1.Text = i1 & i2 & i3 & i4 & i5
Next
Next
Next
Next
Next
End Sub

Function Squ(x)
If Sqr(x) = Math.Round(Sqr(x)) Then Squ = 1 Else Squ = 0
End Function


IPBLE:  Increasing Performance By Lowering Expectations.

#25 2005-12-24 11:33:43

krassi_holmz
Real Member

Offline

Re: Very interesting problems..

...n<>6


IPBLE:  Increasing Performance By Lowering Expectations.

Board footer

Powered by FluxBB