You are not logged in.

- Topics: Active | Unanswered

**seerj****Member**- Registered: 2005-12-21
- Posts: 42

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

Offline

**seerj****Member**- Registered: 2005-12-21
- Posts: 42

Please...help me!

Waiting for ur help

Happy Holidays

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

what means that the sum is perfect square?

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

√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..."

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

"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)*

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

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Then Q && R = N.

How exactly would you say "&&"?

Offline

**seerj****Member**- Registered: 2005-12-21
- Posts: 42

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

Offline

**seerj****Member**- Registered: 2005-12-21
- Posts: 42

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!

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

&& 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)*

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Here is ss with 7 numbers:

1 8 17 19 6 10 15

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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)*

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

I've loved this sequence!

I'm starting with making programs tommorow morning, because it's too late now.

See you!

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**seerj****Member**- Registered: 2005-12-21
- Posts: 42

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!!!!

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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?

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

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.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

...n<>6

IPBLE: Increasing Performance By Lowering Expectations.

Offline