# increasing / decreasing number algorithm (recursive)

• July 9th 2008, 04:38 PM
angel.white
increasing / decreasing number algorithm (recursive)
Working on a Project Euler problem, Bouncy numbers are defined as numbers which are not increasing or decreasing. I wrote an algorithm that determines if a number is bouncy, but I need to check a large quantity of numbers, and running each number through the algorithm is would take an extremely long time.

So I am trying to write a function that will generate all non-bouncy numbers, basically generate increasing numbers, and decreasing numbers, and then subtract the duplicates (numbers where all digits are the same).

According to my bouncy algorithm, there are 475 numbers below 1000 which are bouncy.

But using my algorithm to generate increasing and decreasing numbers, I get 220 (for each) below 1000, which is a total of 440, which is less than the 475 expected (and I haven't even subtracted duplicates yet). So I am somehow missing numbers, but I can't figure out which :/

(explanation of the increasing function, if you need it, both increasing and decreasing work the same way)
The program I created is a recursive function, which increments each digit from the predecessor's value up to 9. If it is on the last digit, ie 56_ will have increasing values: 566, 567, 568, 569 so it returns 10-6=4

It keeps track of these sums along the way.

To invoke, execute input(0,n) where n is the number of digits, ie the increasing numbers below 100 would be input(0,2) the increasing numbers below a million would be input(0,6)

To invoke the decreasing function, execute input(9,n) which would then calculate all decreasing numbers below the number $9_19_29_3...9_n$

Here is my code, written in Ruby:

Code:

#recursive function that calculates increasing numbers def increase(n, digit)   return 10-n if digit==1   sum=0   while n < 10     sum += increase(n, digit-1)     n+=1   end     return sum end #recursinve function that calculates decreasing numbers def decrease(n, digit)   return n+1 if digit==1   sum=0   while n >= 0     sum += decrease(n, digit-1)     n-=1   end     return sum end #find how many increasing and decreasing 3 digit numbers -- meaning numbrs below 1000 print increase(0, 3), ", ", decrease(9,3) #output is "220, 220"
I don't know why it is not working, in my head it seems it should be correct, and I had it calculate numbers below 100, which would be found by sending increase(0,2) , and decrease(9,2) it returned 55 for each, which I verified with pencil/paper.

Can someone smarter than me help me figure out what's wrong with it?
• July 10th 2008, 03:07 AM
CaptainBlack
Quote:

Originally Posted by angel.white
Working on a Project Euler problem, Bouncy numbers are defined as numbers which are not increasing or decreasing. I wrote an algorithm that determines if a number is bouncy, but I need to check a large quantity of numbers, and running each number through the algorithm is would take an extremely long time.

So I am trying to write a function that will generate all non-bouncy numbers, basically generate increasing numbers, and decreasing numbers, and then subtract the duplicates (numbers where all digits are the same).

According to my bouncy algorithm, there are 475 numbers below 1000 which are bouncy.

According to the problem page there are 525 bouncy numbers below 1000, and I can confirm that this is correct.

Quote:

But using my algorithm to generate increasing and decreasing numbers, I get 220 (for each) below 1000, which is a total of 440, which is less than the 475 expected (and I haven't even subtracted duplicates yet). So I am somehow missing numbers, but I can't figure out which :/

(explanation of the increasing function, if you need it, both increasing and decreasing work the same way)
The program I created is a recursive function, which increments each digit from the predecessor's value up to 9. If it is on the last digit, ie 56_ will have increasing values: 566, 567, 568, 569 so it returns 10-6=4

It keeps track of these sums along the way.

To invoke, execute input(0,n) where n is the number of digits, ie the increasing numbers below 100 would be input(0,2) the increasing numbers below a million would be input(0,6)

To invoke the decreasing function, execute input(9,n) which would then calculate all decreasing numbers below the number $9_19_29_3...9_n$

Here is my code, written in Ruby:

[code]#recursive function that calculates increasing numbers
def increase(n, digit)
return 10-n if digit==1
sum=0
while n < 10
sum += increase(n, digit-1)
n+=1
end

return sum
end

#recursinve function that calculates decreasing numbers
def decrease(n, digit)
return n+1 if digit==1
sum=0
while n >= 0
sum += decrease(n, digit-1)
n-=1
end

return sum
end

Since your algorithm seems to give eroneous answers is it really worth checking this code?

(I could give you the correct answer if you like, but that would not be in the spirit of Project Euler).

RonL
• July 10th 2008, 04:21 AM
Opalg
Quote:

Originally Posted by angel.white
I had it calculate numbers below 100, which would be found by sending increase(0,2) , and decrease(9,2) it returned 55 for each, which I verified with pencil/paper.

Judging from this, I suspect that your error is that you are overlooking the fact that a number cannot start with an initial 0. In fact, there are 45 increasing two-digit numbers (9 in the teens, 8 in the 20s, and so on up until 1 in the 90s). There are 54 decreasing two-digit numbers (2 in the teens (namely 10 and 11), 3 in the 20s, and so on up until 10 in the 90s).

A bouncy number less than 1000 must have three digits. Say the number is abc (where a is the hundreds digit, b the tens digit and c the units digit). Then a must lie between 1 and 9, but b or c might be 0.
• July 10th 2008, 05:10 AM
CaptainBlack
Quote:

Originally Posted by angel.white

I don't know why it is not working, in my head it seems it should be correct, and I had it calculate numbers below 100, which would be found by sending increase(0,2) , and decrease(9,2) it returned 55 for each, which I verified with pencil/paper.

Can someone smarter than me help me figure out what's wrong with it?

How are you classifying the numbers from 1-9? These should not be counted as bouncy.

The number of strictly increasing 2 digit numbers is:

8+7+6+5+4+3+2+1=36

The number of strictly dereasing 2 digit numbers is:

9+8+7+6+5+4+3+2+1=45.

Number of both increasing and decreasing numbers is 9.

This gives a total of 90 increasing or decreasing 2 digit numbers, which is all of them.

RonL
• July 10th 2008, 07:49 AM
angel.white
Quote:

Originally Posted by CaptainBlack
According to the problem page there are 525 bouncy numbers below 1000, and I can confirm that this is correct.

My apologies, I meant not bouncy. 1000-525 = 475 not bouncy numbers
Quote:

Originally Posted by CaptainBlack
(I could give you the correct answer if you like, but that would not be in the spirit of Project Euler).

I would not enjoy that either.
Quote:

Originally Posted by Opalg
Judging from this, I suspect that your error is that you are overlooking the fact that a number cannot start with an initial 0. In fact, there are 45 increasing two-digit numbers (9 in the teens, 8 in the 20s, and so on up until 1 in the 90s). There are 54 decreasing two-digit numbers (2 in the teens (namely 10 and 11), 3 in the 20s, and so on up until 10 in the 90s).

A bouncy number less than 1000 must have three digits. Say the number is abc (where a is the hundreds digit, b the tens digit and c the units digit). Then a must lie between 1 and 9, but b or c might be 0.

I was going to correct for this by subtracting duplicated numbers, but even if I double the numbers I get, I am still short, I was going to subtract 1 for the number zero, then 9(digits-1) for duplicated numbers (I use -1 because my code doesn't actually double count the single digit numbers). So for all below 100, I would get 2(55) -1 -9(2-1) = 100

But I'm mostly interested in how come I have too few increasing / decreasing numbers. These other things I don't expect to have a problem with, but I've tried this problem on 2 separate occasions and keep getting too few possibilities.

For example, the 475 below 1000, I should get (475+1+9(3-1) )/2 = 247 numbers each for increasing and decreasing, but I'm getting 220, so I am somehow not counting relevant numbers.
Quote:

Originally Posted by CaptainBlack
How are you classifying the numbers from 1-9? These should not be counted as bouncy.

The number of strictly increasing 2 digit numbers is:

8+7+6+5+4+3+2+1=36

The number of strictly dereasing 2 digit numbers is:

9+8+7+6+5+4+3+2+1=45.

Number of both increasing and decreasing numbers is 9.

This gives a total of 90 increasing or decreasing 2 digit numbers, which is all of them.

RonL

I've been using the definitions here Problem 113 - Project Euler which would have them as both increasing and decreasing. My actual algorithm counts them with increasing numbers, because it starts at 000 and so for 000 through 009, the ones digit is greater than or equal to the tens digit. It does not calculate them for decreasing because decreasing starts at 999, so for 001 through 009, the ones digit is greater than the tens digit.

So they only get counted once, then I correct for counting 000 by subtracting from the final sum.
• July 10th 2008, 08:06 AM
angel.white
An easier way of seeing what I did might be like this

total_increasing=0
for digit_1 from 0 through 9
for digit_2 from digit_1 through 9
...
for digit_n from digit_(n-1) through 9
total_increasing = total_increasing + 1
end_1
end_2
...
end_n

-------------------------------------------------------
(colour added to make it easier to see)

example for 100:

total_increasing=0
for digit_1 from 0 through 9
for digit_2 from digit_1 through 9
total_increasing = total_increasing + 1
end
end

-------------------------------------------------------
example for 1000:

total_increasing=0
for digit_1 from 0 through 9
for digit_2 from digit_1 through 9
for digit_3 from digit_2 through 9
total_increasing = total_increasing + 1
end
end
end

-------------------------------------------------------

This is what my code essentially does, I use the recursion so that I can easily change the number of digits and not have to manually code in 100 variables. I checked this code against my code, and it returned the same answers, 55, and 220. But if I get the same number of decreasing (which I currently am), then 220*2 = 440 which is less than 475, so even though it is double counting some numbers, which I will correct later, it must also be not counting some numbers, which is higher priority at the moment. After I multiply it by 2, he answer from this code should be greater than the not bouncy numbers.
• July 10th 2008, 12:46 PM
CaptainBlack
Quote:

Originally Posted by angel.white
My apologies, I meant not bouncy. 1000-525 = 475 not bouncy numbers
I would not enjoy that either.
I was going to correct for this by subtracting duplicated numbers, but even if I double the numbers I get, I am still short, I was going to subtract 1 for the number zero, then 9(digits-1) for duplicated numbers (I use -1 because my code doesn't actually double count the single digit numbers). So for all below 100, I would get 2(55) -1 -9(2-1) = 100

But I'm mostly interested in how come I have too few increasing / decreasing numbers. These other things I don't expect to have a problem with, but I've tried this problem on 2 separate occasions and keep getting too few possibilities.

For example, the 475 below 1000, I should get (475+1+9(3-1) )/2 = 247 numbers each for increasing and decreasing, but I'm getting 220, so I am somehow not counting relevant numbers.

I've been using the definitions here Problem 113 - Project Euler which would have them as both increasing and decreasing. My actual algorithm counts them with increasing numbers, because it starts at 000 and so for 000 through 009, the ones digit is greater than or equal to the tens digit. It does not calculate them for decreasing because decreasing starts at 999, so for 001 through 009, the ones digit is greater than the tens digit.

So they only get counted once, then I correct for counting 000 by subtracting from the final sum.

see problem 112 for more context, there it clearly states there are no bouncy numbers below 100.

RonL
• July 10th 2008, 01:05 PM
CaptainBlack

Let $n(k,r)$ denote the number of increasing numbers with $k$ digits ending with digit $r$.

Then:

$n(k+1,0)=n(k,0)$

$n(k+1,1)=2n(k,0)+n(k,1)$

etc,

So in general:

$n(k+1,r)=\sum_{\rho=0}^r (\rho+1) n(k,r-\rho), \ \ \ r=0,1,..9$

and something similar for decreasing number.

RonL
• July 10th 2008, 07:40 PM
angel.white
Quote:

Originally Posted by CaptainBlack
see problem 112 for more context, there it clearly states there are no bouncy numbers below 100.

RonL

I think we might be miscommunicating, I am trying to count not bouncy numbers, so I should be counting all numbers below 100, and currently I am: 55(increasing) + 55(decreasing) - 9(duplicated) -1(zero) = 100(~bouncy)

Hmm, maybe I should be arriving at the number 99 instead of 100. Perhaps I am counting zero twice, so it should subtract 10 duplicated instead of 9. But regardless, I'm getting about what I would expect for less than 100, but pretty different for less than 1000.
Quote:

Originally Posted by CaptainBlack

Let $n(k,r)$ denote the number of increasing numbers with $k$ digits ending with digit $r$.

Then:

$n(k+1,0)=n(k,0)$

$n(k+1,1)=2n(k,0)+n(k,1)$

etc,

So in general:

$n(k+1,r)=\sum_{\rho=0}^r (\rho+1) n(k,r-\rho), \ \ \ r=0,1,..9$

and something similar for decreasing number.

RonL

Okay, so
n(2,0) counts [ $\emptyset$] = n(1,0) counts [ $\emptyset$]
which has a cardinality of 0

n(2,1) counts [11] = 2*n(1,0) counts [ $\emptyset$] + n(1,1) counts [1]
so n(1,1) = n(2,1) = 1

and in general, if r > 0 then n(1,r) = 1
and if r = 0 then n(k,0) = 0

--------------------------------------------------------
Okay, I'll try for k+1=2, r=5

n(2,5) = sum of:
(0+1) n(1,5) = 1*1 = 1
(1+1) n(1,4) = 2*1 = 2
(2+1) n(1,3) = 3*1 = 3
(3+1) n(1,2) = 4*1 = 4
(4+1) n(1,1) = 5*1 = 5
(5+1) n(1,0) = 6*1 = 0

= 15 elements

which is counting:
cardinality of [11,12,13,14,15, 22,23,24,25, 33,34,35, 44,45, 55]= 15

So that looks correct.

--------------------------------------------------------
Now I'll try for k+1=3, r=5

n(3,5) = sum of:
(0+1)n(2,5) = 1*[(0+1)n(1,5) + (1+1)n(1,4) + (2+1)n(1,3) + (3+1)n(1,2) + (4+1)n(1,1) + (5+1)n(1,0)] = 1*(1+2+3+4+5) = 15

(1+1)n(2,4) = 2*[(0+1)n(1,4) + (1+1)n(1,3) + (2+1)n(1,2) + (3+1)n(1,1) + (4+1)n(1,0)] = 2*(1+2+3+4) = 20

(2+1)n(2,3) = 3*[(0+1)n(1,3) + (1+1)n(1,2) + (2+1)n(1,1) + (3+1)n(1,0)] = 3*(1+2+3) = 18

(3+1)n(2,2) = 4*[(0+1)n(1,2) + (1+1)n(1,1) + (2+1)n(1,0)] = 4*(1+2) = 12

(4+1)n(2,1) = 5*[(0+1)n(1,1) + (1+1)n(1,0)] = 5

(5+1)n(2,0) = 6*[(0+1)n(1,0)] = 0

= 15+25+18+12+5 = 75

But I'm not sure if this is correct, I'm counting:

[011,012,013,014,015,
022,023,024,025,
033,034,035,
044,045,
055
(=15)

111,112,113,114,115
122,123,124,125
133,134,135
144,145
155
(=15)

222,223,224,225
233,234,235,
244,245
255
(=10)

333,334,335
344,345
355
(=6)

444,445
455
(=3)

555
(=1)]

so cardinality = 50

which is:
6 groups of 1 = 6
5 groups of 2 = 10
4 groups of 3 = 12
3 groups of 4 = 12
2 groups of 5 = 10

=50
• July 11th 2008, 04:55 AM
angel.white
Quote:

Originally Posted by CaptainBlack
$n(k+1,r)=\sum_{\rho=0}^r (\rho+1) n(k,r-\rho), \ \ \ r=0,1,..9$

Well I programmed it in and got:
70 for n(3,5)
15 for n(2,5)
495 for n(3,9)

edit: also, I just tried n(2,9) and got 45

Code:

def n(k,r)   return 1 if k==1   return 0 if r==0     sum=0   for p in 0...r     sum+=(p+1) * n(k-1,r-p)   end     return sum end   puts n(3,5), n(2,5), n(3,9)
But I still don't see why the for loop method discussed in post #6 returns the wrong number. If I understood why that method is wrong, I could probably fix my code myself.
• July 24th 2008, 10:09 AM
angel.white
If anyone cares, the discrepancy was in decreasing numbers ending in zero:

it would add for example, 0123 and 3210 but not 321. I got around this by all the decreasing functions below it. Then to correct, they will overlap when all digits are the same, ie 000, 111, ..., 999, and 00, 11, ..., 99, and 0,1,...,9 so I subtracted ten for each digit. And since zero gets added to the sum, subtract 1 for zero as well.

For example, 1000 would be:

(increasing for 3 digits = 220) + (decreasing for 3 digits=220) + (decreasing for 2 digits=55) + (decreasing for 1 digit=10) - (10*3 digits = 30 ) - (1 for zero = 1)

220+200+55+10-30-1 = 474

Now I will go about optimizing and consolidating ^_^

edit: Well, got it solved (ended up using excel O.o)