Very interesting problems..

seerj · 2005-12-21 05:22:54

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

seerj · 2005-12-23 01:47:32

Please...help me!

Waiting for ur help

Happy Holidays

Ricky · 2005-12-23 04:50:04

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.

krassi_holmz · 2005-12-23 06:48:53

what means that the sum is perfect square?

Ricky · 2005-12-23 06:52:58

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

krassi_holmz · 2005-12-23 07:21:23

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.

Ricky · 2005-12-23 07:40:49

"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-23 07:42:26)

krassi_holmz · 2005-12-23 07:42:19

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

Ricky · 2005-12-23 07:45:38

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.

krassi_holmz · 2005-12-23 07:51:07

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.

Ricky · 2005-12-23 10:43:48

Then Q && R = N.

How exactly would you say "&&"?

seerj · 2005-12-23 11:07:43

&& 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..

seerj · 2005-12-23 11:10:10

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!

krassi_holmz · 2005-12-23 11:29:04

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.

Ricky · 2005-12-23 11:36:17

&& 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-23 11:38:02)

krassi_holmz · 2005-12-23 11:41:02

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

krassi_holmz · 2005-12-23 11:46:01

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

Ricky · 2005-12-23 12:05:44

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-23 12:22:49)

krassi_holmz · 2005-12-23 12:10:03

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-23 12:16:44)

krassi_holmz · 2005-12-23 12:15:29

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

krassi_holmz · 2005-12-23 12:18:52

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.

seerj · 2005-12-23 12:23:45

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

However thanx to all!!!!

Ricky · 2005-12-23 12:24:12

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?

krassi_holmz · 2005-12-23 12:31:07

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

krassi_holmz · 2005-12-23 12:33:43

...n<>6

Math Is Fun Forum

#1 2005-12-21 05:22:54

Very interesting problems..

#2 2005-12-23 01:47:32

Re: Very interesting problems..

#3 2005-12-23 04:50:04

Re: Very interesting problems..

#4 2005-12-23 06:48:53

Re: Very interesting problems..

#5 2005-12-23 06:52:58

Re: Very interesting problems..

#6 2005-12-23 07:21:23

Re: Very interesting problems..

#7 2005-12-23 07:40:49

Re: Very interesting problems..

#8 2005-12-23 07:42:19

Re: Very interesting problems..

#9 2005-12-23 07:45:38

Re: Very interesting problems..

#10 2005-12-23 07:51:07

Re: Very interesting problems..

#11 2005-12-23 10:43:48

Re: Very interesting problems..

#12 2005-12-23 11:07:43

Re: Very interesting problems..

#13 2005-12-23 11:10:10

Re: Very interesting problems..

#14 2005-12-23 11:29:04

Re: Very interesting problems..

#15 2005-12-23 11:36:17

Re: Very interesting problems..

#16 2005-12-23 11:41:02

Re: Very interesting problems..

#17 2005-12-23 11:46:01

Re: Very interesting problems..

#18 2005-12-23 12:05:44

Re: Very interesting problems..

#19 2005-12-23 12:10:03

Re: Very interesting problems..

#20 2005-12-23 12:15:29

Re: Very interesting problems..

#21 2005-12-23 12:18:52

Re: Very interesting problems..

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

Re: Very interesting problems..

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

Re: Very interesting problems..

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

Re: Very interesting problems..

#25 2005-12-23 12:33:43

Re: Very interesting problems..

Board footer