## 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.

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 […]

```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
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 = \$_; my \$count = \$_; 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 = \$_;
my \$count = \$_;
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&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&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;
}
```