
Topic review (newest first)
 Ricky
 20060118 03:25:03
Got my program down to 0.371 seconds when doing 232 by calculating where the next perfect root will be instead of linearly searching for it.
 Ricky
 20060116 04:53:59
There must exist i0 element of N : for every i>=i0 a_(i+2)a_i<i.
You haven't defined N, a_, or F() or n. I have no idea what these are.
 krassi_holmz
 20060116 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
 20060116 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
 20060116 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
 20060116 00:45:11
 Ricky
 20060111 07:11:52
Quite odd, mine works completely fine, even overnight.
 seerj
 20060111 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
 20060111 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
 20060111 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
 20060110 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
 20060110 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
 20060109 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
 20060109 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
 20060109 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.
