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.
Programming Praxis 
[…] 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 […]
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 . politeshere 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));;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)
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:]]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";
}
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"; }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]
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)) printA 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 endin 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) ]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; };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;
}
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;
}
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; }