## Polite Numbers

### December 17, 2010

A number is polite if it can be written as the sum of two or more consecutive numbers; for instance, 7 is polite because it can be written at 3 + 4. Some numbers can be written as the sum of two or more consecutive numbers in more than one way; for instance, 15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8. The number of ways that a number can be written as the sum of two or more consecutive numbers is its politeness. Any number that is a power of 2 cannot be written as the sum of two or more consecutive numbers; such a number has a politeness of 0, and is thus impolite.

There is a set of consecutive integers that sum to a given number for each odd divisor of the number greater than 1. For instance, the divisors of 28 are 1, 2, 4, 7, 14, 28. The only odd divisor of 28 greater than 1 is 7, so 28 has a politeness of 1. The set of consecutive integers has length 7 (the divisor) and is centered at 4 = 28 ÷ 7: 1 + 2 + 3 + 4 + 5 + 6 + 7; that works because there are 7 numbers with an average of 4 (since they are centered on 4). In some cases, such as the divisor 11 of the number 33, the set of numbers includes negative integers: -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8; in that case, the negative integers cancel out the corresponding positive integers, so the remaining set is 3 + 4 + 5 + 6 + 7 + 8 = 33.

Your task is to write a program that calculates all the ways that a number can be written as the sum of two or more consecutive numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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;
}
```