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

You are not logged in.

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

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

Re: Very interesting problems..

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


Why did the vector cross the road?
It wanted to be normal.

Offline

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

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

Re: Very interesting problems..

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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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 neutral He was near the solution...I dunno how. As soon as my uni starts i ask to my friend to show me it

Offline

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

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

Re: Very interesting problems..

krassi_holmz wrote:

But is really 32 the minimum?

Yes neutral 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

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

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

Re: Very interesting problems..

So the problem is mathematical, not programmical.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

How old are you Seerj


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

John, i' explain later.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

How to produce ">" in LaTeX?


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

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

View Image: squared.GIF

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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

my friend is winning the contest tongue..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

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

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

Re: Very interesting problems..

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


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

Give some program code.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

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

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

Re: Very interesting problems..

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

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

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

Re: Very interesting problems..

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


"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

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

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

Re: Very interesting problems..

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.


"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

Board footer

Powered by FluxBB