Very interesting problems..

mathsyperson · 2005-12-30 04:57:24

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

krassi_holmz · 2005-12-30 05:31:56

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

seerj · 2005-12-30 05:41:43

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

seerj · 2005-12-30 05:44:10

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)

krassi_holmz · 2005-12-30 06:15:08

So the problem is mathematical, not programmical.

krassi_holmz · 2005-12-30 06:27:22

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.

krassi_holmz · 2005-12-30 06:35:01

How old are you Seerj

krassi_holmz · 2005-12-30 06:39:40

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

krassi_holmz · 2005-12-30 07:05:34

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)

John E. Franklin · 2005-12-30 07:24:03

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?

krassi_holmz · 2005-12-30 07:26:11

John, i' explain later.

krassi_holmz · 2005-12-30 07:41:44

How to produce ">" in LaTeX?

krassi_holmz · 2005-12-30 07:49:45

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)

krassi_holmz · 2006-01-02 05:30:02

I generalized my first result:
n>13!!!
It seems my square function is useful.

I'll post proof soon.

krassi_holmz · 2006-01-02 06:08:45

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
n>13

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

krassi_holmz · 2006-01-02 07:30:24

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

Yes, this does mean intersection.

seerj · 2006-01-07 00:39:05

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?

krassi_holmz · 2006-01-07 03:00:14

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

krassi_holmz · 2006-01-07 03:03:25

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

Ricky · 2006-01-07 06:41:31

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.

Ricky · 2006-01-07 06:53:53

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)

krassi_holmz · 2006-01-07 07:45:13

Give some program code.

Ricky · 2006-01-07 07:58:37

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

Ricky · 2006-01-07 08:03:13

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;
}

Ricky · 2006-01-07 08:07:01

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.

Math Is Fun Forum

#126 2005-12-30 04:57:24

Re: Very interesting problems..

#127 2005-12-30 05:31:56

Re: Very interesting problems..

#128 2005-12-30 05:41:43

Re: Very interesting problems..

#129 2005-12-30 05:44:10

Re: Very interesting problems..

#130 2005-12-30 06:15:08

Re: Very interesting problems..

#131 2005-12-30 06:27:22

Re: Very interesting problems..

#132 2005-12-30 06:35:01

Re: Very interesting problems..

#133 2005-12-30 06:39:40

Re: Very interesting problems..

#134 2005-12-30 07:05:34

Re: Very interesting problems..

#135 2005-12-30 07:24:03

Re: Very interesting problems..

#136 2005-12-30 07:26:11

Re: Very interesting problems..

#137 2005-12-30 07:41:44

Re: Very interesting problems..

#138 2005-12-30 07:49:45

Re: Very interesting problems..

#139 2006-01-02 05:30:02

Re: Very interesting problems..

#140 2006-01-02 06:08:45

Re: Very interesting problems..

#141 2006-01-02 07:30:24

Re: Very interesting problems..

#142 2006-01-07 00:39:05

Re: Very interesting problems..

#143 2006-01-07 03:00:14

Re: Very interesting problems..

#144 2006-01-07 03:03:25

Re: Very interesting problems..

#145 2006-01-07 06:41:31

Re: Very interesting problems..

#146 2006-01-07 06:53:53

Re: Very interesting problems..

#147 2006-01-07 07:45:13

Re: Very interesting problems..

#148 2006-01-07 07:58:37

Re: Very interesting problems..

#149 2006-01-07 08:03:13

Re: Very interesting problems..

#150 2006-01-07 08:07:01

Re: Very interesting problems..

Board footer