Results 1 to 11 of 11

Math Help - increasing / decreasing number algorithm (recursive)

  1. #1
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1

    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:

    Note: # denotes comments
    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by angel.white View Post
    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.

    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:

    Note: # denotes comments
    [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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by angel.white View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by angel.white View Post

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    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 View Post
    (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 View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    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.
    Last edited by angel.white; July 10th 2008 at 06:20 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by angel.white View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    How about this:

    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    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 View Post
    How about this:

    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    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)
    Last edited by angel.white; July 24th 2008 at 11:50 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Where a function is increasing/decreasing?
    Posted in the Calculus Forum
    Replies: 10
    Last Post: October 14th 2009, 03:27 AM
  2. increasing or decreasing
    Posted in the Calculus Forum
    Replies: 2
    Last Post: July 14th 2009, 07:02 PM
  3. Increasing/Decreasing
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 16th 2009, 06:06 PM
  4. Increasing/Decreasing and Abs Max and Min
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 28th 2009, 05:57 PM
  5. increasing decreasing
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 6th 2007, 01:29 PM

Search Tags


/mathhelpforum @mathhelpforum