Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

How about a chain of length 1? Or 0, even.

Why did the vector cross the road?

It wanted to be normal.

Offline

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

Yes, but actually length =0 and length=1 are trivial.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

Yeah.. i dunno how did it! The one btw.. Instead one of my friend has shown why there isn't any circular number with

n<31 He was near the solution...I dunno how. As soon as my uni starts i ask to my friend to show me it

Offline

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

krassi_holmz wrote:

But is really 32 the minimum?

Yes My teacher [who is a math researcher] write : MINIMUM N is 32

Now he's asking why..

And he would see other sequences longer than tat boy's one

*Last edited by seerj (2005-12-30 05:44:46)*

Offline

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

So the problem is mathematical, not programmical.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

Let start.

for any square s

s==0,1(mod 4).

So the sum of two conseuense numbers must be ==0,1(mod 4).

We have this cases:

If n == 0 (mod 4) then the neightbours of n must be == 0,1 (mod 4)

If n == 1 (mod 4) then the neightbours of n must be == 3,0 (mod 4)

If n == 2 (mod 4) then the neightbours of n must be == 2,3 (mod 4)

If n == 3 (mod 4) then the neightbours of n must be == 1,2 (mod 4)

That's a begining.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

How old are you Seerj

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

When you have the proof please don't post it immediately. I want to test myself.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

I got interesting results. But first I have to define a function:

Let

is the smallest perfect square greater than n.

We have that sq↑[x]>x.

Let sq↑[sq↑[sq↑[...sq↑[x]]]]=sq↑n[x]

*Last edited by krassi_holmz (2005-12-30 07:45:11)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

I followed your logic until you said "But we have

at least 2 squares greater than n

at least 2 squares greater than n-1".

What does this mean? Can you give numerical example?

**igloo** **myrtilles** **fourmis**

Offline

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

John, i' explain later.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

How to produce ">" in LaTeX?

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

Let look at the neightbours of n in chain with length n amd maxNumber n:

{...,x,n,y,...}

We take that n>x>y. Then n+x and n+y are perfect squares, so:

n+x > n+y =>

Let

Then

so

So when there does not exist chain with Length n and MaxNumber n.

From the upper equation we get:

=>

=>

for 0 ≤ n < 5.8 there doesn't exist that kind of chain, so

n>5.

*Last edited by krassi_holmz (2006-01-02 05:26:36)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

I generalized my first result:

n>13!!!

It seems my square function is useful.

I'll post proof soon.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

Here is it:

We will define two more functions:

We have chain CH.

Let

is the left neigtbour of number i and

is the right neightbour of i.

Then the sums

and

must be perfect squares, so:

1. If

then

and

So generally

<< ----- (1)

2. When

we get the same as (1) ,so (1) is for all i<n (n=CH.length)

Now to summarize ner[i] and nei[i]:

So

But, from (1) follows:

So if n is "squarible" we must have

I used a computer program to compute the first members and for

n<14 all are negative, so

*Last edited by krassi_holmz (2006-01-02 06:39:47)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

Ricky wrote:

&& 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 3Hold 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?

Yes, this does mean intersection.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

my friend is winning the contest ..He's the only person who shown why 32 is the minimum number.

But there is another boy who found a 59 lenght sequence!!!!!

1,3,6,10,15,21,4,5,11,14,50,31,18,7,2,23,58,42,39,25,56,8,17,32,49,51, 13,36,28,53,47,34,30,19,45,55,26,38,43,57,24,12,37,44,20,29,52,48,33,16, 9,40,41,59,22,27,54,46,35

Krassi did u find an algorithm to create any circular sequences?

Offline

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

Please, seerj, tell us how did he done it.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

I'l try full logic examination program. It will proof that 32 is the minimal, but it will be very slow.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

I'm doing the same Krassi. I had it done before, but I realized that a method I used to cut down on execution time just eliminated some needed tests. So I'm back to my original program. It takes O(n!) time, right now it's on size 12 and has to do 479,001,600 comparisons.

"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

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

Hah! I am so stupid...

The way my algorithm works is that it builds a list of numbers, then tests them. I completely forgot that I could test them while building, and stop building them if I run into a combination that doesn't work!

My program tried all possible combinations from lists of size 2 to 32 in 0.82 seconds, and found the one at 32.

*Last edited by Ricky (2006-01-07 06:56:22)*

"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

Give some program code.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

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

Alright, here is the psuedo code:

Declare three arrays: base (integer), used (boolean), and test (integer)

main:

From size = 2 to size = 32 (or whatever numbers you wan't)

clear all three lists so they have 0 elements

From gen = 1 to gen = size

add gen to base

add false to used

testVals(base, used, test)

testVals: recieves arrays base (integer), used (boolean), test (integer)

if test size is equal to base size

test the list to make sure all adjacent values are perfect squares, then output if they are

return (exit the function)

else

From x = 0 to x = size of used

if used[x] == false //you have yet to use this number in the list

if x != 0 //don't compare 0 because 0 - 1 is not in the array

if compare(test[x], test[x-1]) is false // see function compare below

continue //skip all the code below, but continue in the current loop

used[x] = true

add base[x] to the back of test

testVals(base, used, test)

remove the last element of test

used[x] = false

compare: recieves x (int), y (int)

if the sqrt of x + y is an integer

return true

return false

"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

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

C++ code:

#include <iostream>

#include <fstream>

#include <vector>

#include <math.h>

#include <windows.h>

using namespace std;

void testVals(vector<int> base, vector<bool> use, vector<int> test);

bool compare(int x, int y);

int main()

{

int start = GetTickCount();

for (int size = 2; size <= 32; size++)

{

cout << "Testing list size " << size << "..." << endl;

vector<int> base;

vector<bool> used;

vector<int> test;

for (int gen = 1; gen <= size; gen++)

{

base.push_back(gen);

used.push_back(false);

}

testVals(base, used, test);

}

int end = GetTickCount();

cout << "Time: " << (end - start) / 1000.0 << endl;

return 0;

}

void testVals(vector<int> base, vector<bool> used, vector<int> test) {

if (test.size() == base.size())

{

bool result = compare(test[test.size()-1], test[0]);

if (result)

{

ofstream o("asdf.txt", ios::app);

o << "Size: " << test.size() << endl;

for (int x = 0; x < test.size(); x++)

{

o << test[x] << " ";

}

o << endl;

}

return;

}

for (int x = 0; x < used.size(); x++)

{

if (used[x] == false)

{

if (x != 0)

{

if (!compare(test[test.size()-1], base[x])) {

continue;

}

}

used[x] = true;

test.push_back(base[x]);

testVals(base, used, test);

test.erase(test.end()-1);

used[x] = false;

}

}

}

bool compare(int x, int y)

{

double temp = sqrt((double)x + y);

const double amount = 0.00001;

if (temp + amount > (int) temp && temp - amount < (int)temp)

{

return true;

}

return false;

}

Offline

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

Oh, and as a note, for each combination it will find two lists. For example, it will find:

Size: 32

1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

Size: 32

1 15 10 26 23 2 14 22 27 9 16 20 29 7 18 31 5 11 25 24 12 13 3 6 30 19 17 32 4 21 28 8

Which are really the same lists, just in reverse order. Since it is a circle, order doesn't matter.

Offline