Polite Numbers

December 17, 2010

The list of numbers corresponding to the odd divisor d of the number n is calculated by the polite function; the first arm of the if is the “normal” case, and the second arm of the if is taken when the list includes 0 or negative numbers:

(define (polite n d)
  (let ((d2 (quotient d 2)) (n/d (/ n d)))
    (if (< d2 n/d)
        (range (- n/d d2) (+ n/d d2 1))
        (range (+ (abs (- n/d d2)) 1) (+ n/d d2 1)))))

We make a list of all the sets of consecutive integers by iterating through the odd divisors of the input number:

(define (polites n)
  (if (= (expt 2 (ilog 2 n)) n) '()
    (let loop ((ds (cdr (filter odd? (divisors n)))) (ps '()))
      (if (null? ds) (reverse ps)
        (loop (cdr ds) (cons (polite n (car ds)) ps))))))

It’s easy to compute the politeness of a number:

(define (politeness n)
  (if (= (expt 2 (ilog 2 n)) n) 0
    (length (cdr (filter odd? (divisors n))))))

Here are some examples:

> (politeness 15)
3
> (polites 15)
((4 5 6) (1 2 3 4 5) (7 8))
> (politeness 28)
1
> (polites 28)
((1 2 3 4 5 6 7))
> (politeness 33)
3
> (polites 33)
((10 11 12) (3 4 5 6 7 8) (16 17))

We used range, filter, sort, unique, and ilog from the Standard Prelude, and factors and divisors from a previous exercise. You can run the program at http://programmingpraxis.codepad.org/YgFEcg8Q.

About these ads

Pages: 1 2

15 Responses to “Polite Numbers”

  1. […] Praxis – Polite Numbers By Remco Niemeijer In today’s Programming Praxis exercise, our task is to list all the ways that a number can be written as the […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2010/12/17/programming-praxis-polite-numbers/ for a version with comments):

    import Data.List
    import Data.Numbers.Primes
    
    divisors :: Integral a => a -> [a]
    divisors = nub . sort . map product . subsequences . primeFactors
    
    polites :: Integral a => a -> [[a]]
    polites n = [ [max (d//2 - n//d + 1) (n//d - d//2)..n//d + d//2]
                | d <- tail $ divisors n, odd d, let (//) = div]
    
    politeness :: Integral a => a -> Int
    politeness = length . polites
    
  3. here my commented solution: http://www.gleocadie.net/?p=519&lang=en

    open List;;
    
    let seq lb ub =
      let rec seq' n res =
        if n >= lb
          then seq' (n-1) (n::res)
          else res
    in seq' ub [];;
    
    let divisors n =
      let module S = Set.Make(struct type t = int let compare = compare end) in
      S.elements (fold_left
                    (fun x -> fun y -> if n mod y = 0
                                         then S.add y x
                                         else x) S.empty (seq 1 n));;
    let polite n =
      let odd1p = (fun x -> x > 1 && x mod 2 = 1) in
      map (fun d -> let y = n / d
                     and d' = d / 2 in
                       seq (max (d' - y + 1) (y - d')) (y + d'))
          (filter odd1p (divisors n));;
    
  4. Tom said

    Hi,
    Here’s my solution in Scala. I’m sure there’s a better way to calculate divisors and also a better way to expand the length of array rather than just incrementing it.


    import scala.collection.mutable._

    object Divisors
    {
    def generate(n:Int) =
    {
    var divisors = ListBuffer[Int]()
    for(i <- 1 to n)
    {
    if(n % i == 0)
    divisors += i
    }
    divisors.toList
    }
    }

    object PoliteNumbers
    {
    def calculate(number:Int) =
    {
    var politeness = 0
    for(divisor 1 && divisor < number && divisor % 2 == 1)
    {
    politeness += 1
    var start = divisor
    var end = divisor
    var sum = 0
    while(sum < number)
    {
    start -= 1
    end += 1
    sum = (start to end).sum
    }
    println(start+" to "+end+" : "+(start to end).sum)
    }
    }
    println("Politeness is "+politeness)
    }

    }
    val number = Integer.parseInt(args(0))
    PoliteNumbers.calculate(number)

  5. Graham said

    Brain’s a little worn out from moving/end of semester, so I Pythoned the Scheme procedures.
    I don’t think that we need to check whether n is a power of 2, because it will have no odd
    divisors if it is.

    
    def ilog(b, n):
        c = 0
        i = b
        while i <= n:
            c += 1
            i *= b
        return c
    
    def odd_divisors(n):
        return [d for d in xrange(1, n + 1) if d % 2 and not n % d]
    
    def politeness(n):
        return len(odd_divisors(n)) - 1
    
    def polite(n, d):
        d2 = d//2
        nd = n//d
        if d2 < nd:
            return range(nd - d2, nd + d2 + 1)
        else:
            return range(abs(nd - d2) + 1, (nd + d2 + 1))
    
    def polites(n):
        return [polite(n, d) for d in odd_divisors(n)[1:]]
    
  6. ye said

    Here is a Perl solution. I hope I uploaded the code correctly


    #!/usr/bin/perl

    print "Enter an integer: ";
    $number = ;
    chomp($number);

    $politeness = 0;

    for($div = 3; $div <= $number; $div += 2) { #iterate through odd potential divisors
    if($number % $div == 0) { #found an odd divisor
    $codiv = $number / $div; #set the codivisor
    printline($codiv-($div-1)/2,$div);
    $politeness++;
    }
    }
    print "Politeness of $number is $politeness\n";

    sub printline
    {
    my $base = $_[0];
    my $count = $_[1];
    if($base < 0) { #cancel off the negative part
    $base = -$base + 1;
    $count = $count - (2*$base) + 1;
    }
    print "$base";
    $count--;
    until($count == 0){
    $base++;
    print " + $base";
    $count--;
    }
    print " = $number\n";
    }

  7. ye said

    Ok, maybe the code will look better like this

    #!/usr/bin/perl
    
    print "Enter an integer: ";
    $number = <STDIN>;
    chomp($number);
    
    $politeness = 0;
    
    for($div = 3; $div <= $number; $div += 2) { #iterate through odd potential divisors
      if($number % $div == 0) { #found an odd divisor
        $codiv = $number / $div; #set the codivisor
        printline($codiv-($div-1)/2,$div);
        $politeness++;
      }
    }
    print "Politeness of $number is $politeness\n";
    
    sub printline 
    {
      my $base = $_[0];
      my $count = $_[1];
      if($base < 0) { #cancel off the negative part
        $base = -$base + 1;
        $count = $count - (2*$base) + 1;
      }
      print "$base";
      $count--;
      until($count == 0){
        $base++;
        print " + $base";
        $count--;
      }
      print " = $number\n";
    }
    
  8. Mike said

    a “functional” python version

    factors(n) returns a sequence of (p,k) tuples, where p^k is in the factorization of “n”

    from itertools import dropwhile, imap, islice, product, repeat, starmap
    from operator import mul

    def geometric_series(p, k):
    ”’return generator for geometric series p^0, p^1, p^2, … p^k.”’

    return (pow(p, n) for n in range(k+1))

    def odd_divisors(n):
    ”’generates all odd divisors of “n”.”’

    odd_factors = dropwhile(lambda t:t[0]&1==0, factors(n))
    sets_of_odd_factors = product(*starmap(geometric_series, odd_factors))
    return imap(reduce, repeat(mul), sets_of_odd_factors, repeat(1))

    def polites(n):
    ”’generates lists of consecutive integers that sum to “n”.”’

    for divisor in islice(odd_divisors(n), 1, None):
    hi = n/divisor + divisor/2
    low = max(hi – divisor + 1, divisor – hi)

    yield range(low,hi+1)

    def politeness(n):
    ”’return number of sequences that sum to “n”.”’

    return sum(imap(bool, odd_divisors(n))) – 1

    #test:
    for n in (28, 33, 42, 64):
    print ‘the politeness of %d is %d:’ % (n, politeness(n))
    for lst in polites(n):
    print ‘ %s = %d’ % (‘ + ‘.join(str(i) for i in lst), sum(lst))
    print

    [/soucecode]

  9. Mike said

    New and improved! Now with formating!

    from itertools import dropwhile, imap, islice, product, repeat, starmap
    from operator import mul
    
    def geometric_series(p, k):
        '''return generator for geometric series p^0, p^1, p^2, ... p^k.'''
        return (pow(p, n) for n in range(k+1))
    
    def odd_divisors(n):
        odd_factors = dropwhile(lambda t:t[0]&1==0, factors(n))
        sets_of_odd_factors = product(*starmap(geometric_series, odd_factors))
        return imap(reduce, repeat(mul), sets_of_odd_factors, repeat(1))
    
    def polites(n):
        for divisor in islice(odd_divisors(n), 1, None):
            hi = n/divisor + divisor/2
            low = max(hi - divisor + 1, divisor - hi)
    
            yield range(low,hi+1)
    
    def politeness(n):
        return sum(imap(bool, odd_divisors(n))) - 1
    
    #test
    for n in (28, 33, 42, 64):
        print 'the politeness of %d is %d:' % (n, politeness(n))
        for lst in polites(n):
            print '   %s = %d' % (' + '.join(str(i) for i in lst), sum(lst))
        print
    
  10. slabounty said

    A ruby version (kind of ugly though) …

    class Integer
        def divisors
            d = []
            1.upto(Math.sqrt(self)) do | i |
                if self % i == 0
                    d << i
                    d << self / i
                end
            end
            d
        end
    
        def politeness_sums
            d = self.divisors
            d.sort.each do |dv|
                if dv != 1 && dv != self && (dv % 2 != 0)
                    center = self/dv
                    b = center - dv/2
                    b = b.abs + 1 if b < 0
                    e = center + dv/2
                    yield Range.new(b, e)
                end
            end
        end
    end
    
    28.politeness_sums do |ps| 
        print "28 = "
        ps.each { |v| print (v==ps.first ? "#{v}" : " + #{v}") }
        puts
    end
    33.politeness_sums do |ps| 
        print "33 = "
        ps.each { |v| print (v==ps.first ? "#{v}" : " + #{v}") }
        puts
    end
    
  11. Khanh Nguyen said

    in F#

    open System
    
    let generate_set (center:int) (length:int) = 
        let upper = center + length / 2
        let lower = center - length / 2
        List.append [lower..center] [center+1..upper] 
    let polite_number (n:int) = 
        [
            for i in 2 .. n do 
                if n % i = 0 && i % 2 = 1 then
                    yield (generate_set (n/i) i)
        ]
    
  12. Here’s a non-optimal method written in JavaScript. Computational time is O(n/2).

    The function will return a 2d array; first value is the starting number, second value is the number of steps that need to be taken. For example if checkNum() returns [[1, 4]] this means to start at 1 and add a total of 4 numbers together in sequence (e.g. 1+2+3+4).

    function checkNum(N){
    	var result = [], i = 2, P;
    	do{
    		P = N / i + (1 - i) / 2;
    		if(Math.floor(P) === P) result.push([P, i]);
    		i++;
    	}while(P >= 2);
    	return result;
    };
    
  13. Bryan Elliott said

    JS Solve:
    function checkNum(N) {
    //We will return arrays of [start, ct]
    var results = [],
    //Longest possible sequence count is 1+2+3+4+…
    //For a given sequence length ct, this is N=(ct^2+ct)/2
    //Solving for ct, we find that the longest possible sequence is…
    maxCt = Math.ceil((Math.sqrt(8*N+1)-1)/2),
    //If N is even, ct cannot be 2.
    ct = ((N&1)==0)?3:2,
    center, frac;
    for (;ct<=maxCt;ct++) {
    center=N/ct, frac=center-Math.floor(center);
    if (
    //we've divided evenly into a sequence of ct (odd
    (frac==0 && (ct&1)==1) ||
    // or even)
    (frac==0.5 && (ct&1)==0)
    ) {
    results.push([center-(ct-1)/2, ct]);
    }
    }
    return results;
    }

  14. Bryan Elliott said

    Trying again, after reading the help…

    function checkNum(N) {
    //We will return arrays of [start, ct]
    var results = [],
    //Longest possible sequence count is 1+2+3+4+...;
    //For a given sequence length ct, this is N=(ct^2+ct)/2
    //Solving for ct, we find that the longest possible sequence is...
    maxCt = Math.ceil((Math.sqrt(8*N+1)-1)/2),
    //If N is even, ct cannot be 2.
    ct = ((N&1)==0)?3:2,
    center, frac;
    for (;ct<=maxCt;ct++) {
    center=N/ct, frac=center-Math.floor(center);
    if (
    //we've divided evenly into a sequence of ct (odd
    (frac==0 && (ct&1)==1) ||
    // or even)
    (frac==0.5 && (ct&1)==0)
    ) {
    results.push([center-(ct-1)/2, ct]);
    }
    }
    return results;
    }

  15. Bryan Elliott said

    One more time. Really should have an edit option.

    function checkNum(N) {
    	//We will return arrays of [start, ct]
    	var results = [],
    		//Longest possible sequence count is 1+2+3+4+...;
    		//For a given sequence length ct, this is N=(ct^2+ct)/2
    		//Solving for ct, we find that the longest possible sequence is...
    		maxCt = Math.ceil((Math.sqrt(8*N+1)-1)/2),
    		//If N is even, ct cannot be 2.
    		ct = ((N&1)==0)?3:2,
    		center, frac;
    	for (;ct<=maxCt;ct++) {
    		center=N/ct, frac=center-Math.floor(center);
    		if (
    			//we've divided evenly into a sequence of ct (odd
    			(frac==0 && (ct&1)==1) ||
    			// or even)
    			(frac==0.5 && (ct&1)==0)
    		) {
    			results.push([center-(ct-1)/2, ct]);
    		}
    	}
    	return results;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 645 other followers

%d bloggers like this: