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

You are not logged in.

#51 2013-04-14 00:06:08

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

Best to see it with an example.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#52 2013-04-14 00:12:36

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

bobbym wrote:

You do not have to stop there. When 31 does not work you try 30 which does. Algorithm is very fast.

Hm, okay, that does work. And it is very fast! Constant speed!

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#53 2013-04-14 00:15:15

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

Hmmm, it is fast but its worst case might be quite slow!

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#54 2013-04-14 00:26:11

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,820
Website

Re: Four Square

bobbym wrote:

Best to see it with an example.

Okay

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#55 2013-04-14 00:28:51

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

I do not think so.

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#56 2013-04-14 00:44:36

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

Here is one where it works fine:

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#57 2013-04-14 01:30:11

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Have you found an example in which it does not work quickly?

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#58 2013-04-14 01:31:14

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

Heck no, why should I hurt my own feelings?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#59 2013-04-14 01:33:53

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Well, in any case, I think the speed will be sufficient for any number.

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#60 2013-04-14 01:35:56

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

Obviously the algorithm must get there the first time or by continually decrementing find the largest square that would work. But he might now have a problem with the subproblem of 3 squares.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#61 2013-04-14 01:40:53

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Oh, yeah, you need to decrement there as well. Can you find an example when the decrement will not work immediately?

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#62 2013-04-14 01:47:11

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

You mean where you would have to decrement the second one? No, not yet.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#63 2013-04-14 01:54:28

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Actually, we need an example where both the first and the second number are decremented.

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#64 2013-04-14 02:04:00

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

Why would we need an example like that?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#65 2013-04-14 02:08:26

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Think about what would happen if only the second number needs decrementing. We could just keep the algorithm running until we get to the second number. We subtract it, the next largest square is the number we started with, all is well. But if both the first and the second numbers need decrementing then running the algorithm to the second number will still need the first number decremented (and it is now the second number).

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#66 2013-04-14 02:26:37

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

I do not think that is true, at least if I am understanding it. The first two are an ordered pair. They are in >= order.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#67 2013-04-14 02:28:13

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Not necessarily. If we need to, we can find the second number first!

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#68 2013-04-14 02:35:50

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

Before you get the first one?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#69 2013-04-14 02:43:12

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Yes. Imagine that the quartuplet for n is (m,k-1,...,...) and that k^2 is the largest square below n-m^2. Then we won't find anything until we run the algorithm for k-1. Then the next largest square below it is n^2 and we get exactly what we needed.

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#70 2013-04-14 02:46:48

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

The algorithm will run sequentially. It is possible to get an expression for the second square by running it twice symbolically.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#71 2013-04-14 02:48:01

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

What?

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#72 2013-04-14 02:51:10

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

The way you can run it with numbers, you can run it with letters. Say n = a; Then the second square according to the recurrence is:

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#73 2013-04-14 02:54:20

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

Ok, so?

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

#74 2013-04-14 02:58:53

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Four Square

I am not sure but there it is. We were talking getting the second largest square without getting the first weren't we?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#75 2013-04-14 03:03:03

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,037

Re: Four Square

No. I was talking about getting the second number from the answer before the first.

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline