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

You are not logged in.

## Post a reply

Write your message and submit
|
Options

## Topic review (newest first)

Ricky
2006-01-18 03:25:03

Got my program down to 0.371 seconds when doing 2-32 by calculating where the next perfect root will be instead of linearly searching for it.

Ricky
2006-01-16 04:53:59

There must exist i0 element of N : for every i>=i0 a_(i+2)-a_i<i.

if n=2 we get

F(i+2)-F(i)>i, i>2;

You haven't defined N, a_, or F() or n.  I have no idea what these are.

krassi_holmz
2006-01-16 03:10:35

Here's nessesery condition:
There must exist i0 element of N : for every i>=i0 a_(i+2)-a_i<i.

With that we can proof that there doesn't exist cicular sequence for which the sums are Fibonacci numbers. (n>2)
if n=2 we get
1,2 It has sum 3 which is fibonacci number.

Now we'll proof that F(i+2)-F(i)>i, i>2;
F(i+2)=F(i+1)+F(i)>2F(i);
So F(i+2)-F(i)>2F(i)-F(i)=F(i)
And F(i)>i for i>2 so there doesn't exist fibonacci sircular sequence with lengh >2.

krassi_holmz
2006-01-16 02:59:54

We can generalize the question:
Let have the set {a_i} elem N. What are the conditions to exist sircular sequence {b_(1..n)} (the sum of every two consecutive members of {b} is element of {a}.

Ricky
2006-01-16 00:53:46

Boy, I thought this thread was finally dead...

But I was wondering if there exist different proof without guessing.

I think there is, if you know enough about Hamiltonian Circuits.  I don't.  But I wouldn't quite call it guessing, just making observations.

krassi_holmz
2006-01-16 00:45:11

Good work!

I just want to continue the Ricky's mind.

Let n>20. Take 18.
But 36-18=18 so
18+x=49; x=31!
So n>31.

But I was wondering if there exist different proof without guessing.

Ricky
2006-01-11 07:11:52

Quite odd, mine works completely fine, even overnight.

seerj
2006-01-11 05:45:55

this is your code. I tried with it but after 6 hours it has crashed

#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-11 04:48:12

For every circle of size n, you must be able to contruct a Hamilton circuit.  So arrange the numbers around in a cirlce, and then draw a line for every two numbers that add up to a perfect square.

To be a ciruit, every number has to have at least two lines connected to it.  It can be observed that 2 won't have two lines going in until 14:

2 + x = perfect square, where x is a natural number not equal to two.  The lowest two perfect squares are 9 and 16 (2 and 1 don't count since x is natural and not 2).  So to get two lines connected to 2:

2 + x = 16, x = 14.

Size 14 is a minimum, when only considering 2.

For n ≥ 14, consider 8.

8 + x = perfect square

The two lowest perfect squares are 9 and 25.

8 + x = 25, x = 17

So size 17 is a minimum.

For n ≥ 17, consider 16.

16 + x = perfect square

The two lowest perfect squares are 25 and 36.

16 + x = 36, x = 20.

This pattern will continue till 32, where every natural number up to and including 32 has a least two lines connected to it.

Ricky
2006-01-11 03:31:05

Would you mind posting your code?  I'm kind of curious as to why it bombed out.

As for a list of 62:

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

seerj
2006-01-10 04:38:12

#### Ricky wrote:

O my.. i let my program running all night long but it  crashed at size 43!!!!!! :\\\

Crashed?  What language did you program it in?

I should have size 62 by the next time I post.

I used visual c++ 6.
The contest is ended. However i say thank u!
Now it's hard to explain why 32 is the minimum number..but u can find an explanation from
http://www.geocities.com/dharwadker/hamilton/main.html  with the Hamilton Algorithm..

Look at here:
http://www.mat.uniroma2.it/~tauraso/Natale/congettura.txt
is made by my teacher.

Ricky
2006-01-10 02:23:52

O my.. i let my program running all night long but it  crashed at size 43!!!!!! :\\\

Crashed?  What language did you program it in?

I should have size 62 by the next time I post.

seerj
2006-01-09 20:17:27

O my.. i let my program running all night long but it  crashed at size 43!!!!!! :\\\

this is the winner of the contest:
size=61

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

seerj
2006-01-09 08:32:11

#### krassi_holmz wrote:

I've developed another algoritm. It generates all square chains and checks if they're circular.
Size 36:
{1, 3, 6, 19, 30, 34, 2, 23, 26, 10, 15, 21, 4, 32, 17, 8, 28, 36, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31, 33, 16, 9, 27, 22, 14, 35}
~5min.
It seems that for all n > 32 there exist a circular sequence. Strange.

Very good Krassi, thanks.
Anyone know why 32 is the minimum number?

I'm running a program made with the Ricky's algorithm but till now [it has been passed 2 hours] it reached n=41..

however THANK U ALL FRIENDS!!

krassi_holmz
2006-01-09 07:14:25

I've developed another algoritm. It generates all square chains and checks if they're circular.
Size 36:
{1, 3, 6, 19, 30, 34, 2, 23, 26, 10, 15, 21, 4, 32, 17, 8, 28, 36, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31, 33, 16, 9, 27, 22, 14, 35}
~5min.
It seems that for all n > 32 there exist a circular sequence. Strange.