## Mathematical Problem

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Mathematical Problem

Hi all , i've this problem
The Cat in the Hat

Background
(An homage to Theodore Seuss Geisel)

The Cat in the Hat is a nasty creature,
But the striped hat he is wearing has a rather nifty feature.

With one flick of his wrist he pops his top off.

Do you know what's inside that Cat's hat?
A bunch of small cats, each with its own striped hat.

Each little cat does the same as line three,
All except the littlest ones, who just say ``Why me?''

Because the littlest cats have to clean all the grime,
And they're tired of doing it time after time!

The Problem
A clever cat walks into a messy room which he needs to clean. Instead of doing the work alone, it decides to have its helper cats do the work. It keeps its (smaller) helper cats inside its hat. Each helper cat also has helper cats in its own hat, and so on. Eventually, the cats reach a smallest size. These smallest cats have no additional cats in their hats. These unfortunate smallest cats have to do the cleaning.

The number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is times the height of the cat whose hat they are in.

The smallest cats are of height one;
these are the cats that get the work done.
All heights are positive integers.
Given the height of the initial cat and the number of worker cats (of height one), find the number of cats that are not doing any work (cats of height greater than one) and also determine the sum of all the cats' heights (the height of a stack of all cats standing one on top of another).

The Input
The input consists of a sequence of cat-in-hat specifications. Each specification is a single line consisting of two positive integers, separated by white space. The first integer is the height of the initial cat, and the second integer is the number of worker cats.

A pair of 0's on a line indicates the end of input.

The Output
For each input line (cat-in-hat specification), print the number of cats that are not working, followed by a space, followed by the height of the stack of cats. There should be one output line for each input line other than the ``0 0'' that terminates input.

Sample Input

216 125
5764801 1679616
0 0

Sample Output

31 671
335923 30275911

However , to find N we have to solve 2 equations simultaneously
num_of_worker_cats = N^number_of_levels ----> ( 1 )
hieght_of_first_cat * ( 1/(N+1) )^number_of_levels = 1 ----> ( 2 )

How can i solve these 2 equations ?! are these equations right ? is there another way to find N ?

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

The height of these cats-in-a-hat is times the height of the cat whose hat they are in.

I think this sentence is missing something. Is it "(1 / (N+1)) times the height of the cat whose hat they are in"?
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

Oh yes , it was lost while copying and pasting , it's a picture! .

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

You equations look right to me. This is what I come up with:

workers = N^levels
height * (N+1)^(-levels) = 1

height = (N+1)^levels

*From now on, log_bl means log base levels

log_bl(height) = N+1
log_bl(workers) = N

log_bl(height) - 1 = log_bl(workers)
log_bl(height) - log_bl(levels) = log_bl(workers)
log_bl(height / levels) = log_bl(workers)

height / levels = workers

Since you are given height and workers as input, you can find levels and then N, the number of cats in each hat. With those you can calculate the rest of the output.
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

Ohh how can i thank you ! , i didn't even think of taking a logarithm to "levels" base ! , i was trying to solve it by ln and log10 but it doesn't work , thnx Colin

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

MatRiX_OvErLoadiNg wrote:Ohh how can i thank you ! , i didn't even think of taking a logarithm to "levels" base ! , i was trying to solve it by ln and log10 but it doesn't work , thnx Colin

No problem.
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

I have been trying to solve this problem again ( after a long time ) , but i have a point here
how did you got
log_bl(height) = N+1
log_bl(workers) = N

form
workers = N^levels
height = (N+1)^levels

!!!

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

I shouldn't have been able to. It's incorrect.
Need information on a function I've posted? Chances are it's at the MSDN.
MXP

Posts: 6506
Joined: Mon Sep 22, 2003 5:27 pm

Yeah i just noticed today !! so how it can be solved !

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

We know w and h, which are
w=n^l
h=(n+1)^l

Taking logarithms and dividing,
log(h)/log(w)=log(n+1)/log(n)
From this, we can find n. I think a fast way would be Newton-Raphson applied to
f(x) = 1/(log(x+1)/log(x)-1) - 1/(log(h)/log(w)-1)

Once you have n, you can easily find everything else.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

Alvaro wrote:From this, we can find n. I think a fast way would be Newton-Raphson applied to
f(x) = 1/(log(x+1)/log(x)-1) - 1/(log(h)/log(w)-1)

I'm not sure i understand this ?!

Blueteeth

Posts: 616
Joined: Thu Sep 25, 2003 9:54 pm
Location: Egypt

Blueteeth wrote:
Alvaro wrote:From this, we can find n. I think a fast way would be Newton-Raphson applied to
f(x) = 1/(log(x+1)/log(x)-1) - 1/(log(h)/log(w)-1)

I'm not sure i understand this ?!

The only root of the function f(x) above is n. I modified the expression log(x+1)/log(x) a little bit (substracted 1 and took the inverse), to make its plot closer to a straight line, so Newton-Raphson works better. You can do this as long as your transformations are one-to-one mappings.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

In code:
Code: Select all
`#include &lt;iostream&gt;#include &lt;cmath&gt;using namespace std;// The function whose root is ndouble f(double x, double h, double w){   return 1/(1-log(x)/log(x+1))-1/(1-log(w)/log(h));}// The derivative of fdouble df(double x){  return (log(x+1)/x-log(x)/(x+1))/(log(x+1)*log(x+1)*(1-log(x)/log(x+1))*(1-log(x)/log(x+1)));}// Computes the root of f using Newton-Raphsonint compute_n(int h, int w){  double x=10; // A first guess. Doesn't matter much  for(int i=0;i<10;++i)    x-=f(x,h,w)/df(x);  return int(floor(x+.5));}int main(){  int h=216,w=125;  int n=compute_n(h,w);  int l=int(floor(log(w)/log(n)+.5));  cout << w << " = " << n << "^" << l << endl;  cout << h << " = " << (n+1) << "^" << l << endl;}`

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA