Ok, this is fun.
We define f (i) = (p ^ i - 1) / (p - 1)
Write k in the form of a funny "base", where the position value i is this f (i).
You do this from the most significant to the least significant figure. So, first we find the largest j such that f (j) & lt = k. Then calculate the quotient and the remainder of k / f (j). Store the factor as q_j and the remainder as r. Now we calculate the quotient and the remainder of r / f (j-1). Save the factor as q_ {j-1} and the remainder again. Now we calculate the factor and the remainder of r / f (j-2). Etc.
This generates the sequence q_j, q_ {j-1}, q_ {j-2}, ..., q_1. (Note that the sequence ends with 1, not 0.) Then we calculate q_j * p ^ j + q_ {j-1} * p ^ (j-1) + ... q_1 * p. What is your N.
Example: k = 9, p = 3. So f (i) = (3 ^ i - 1) / 2. f (1) = 1, f (2) = 4, f (3) = 13. Thus, the largest j with f (j) <= 9 is equal to i = 2 with f (2) = 4. Take the factor and the remainder from 9/4. What is factor 2 (which is the figure in our 2nd place) and the remainder is from 1.
For this remainder of 1, find the quotient and the rest of 1 / f (1). The coefficient is 1, the remainder is zero, so we are done.
So q_2 = 2, q_1 = 1. 2 * 3 ^ 2 + 1 * 3 ^ 1 = 21, which is the correct N.
I have an explanation on paper why this works, but I'm not sure how to convey it in the text ... Note that f (i) answers the question: "How many factors p is in (p ^ i)!". As soon as you find the largest i, j such that j * f (i) is less than k, and understand what you really do is find the largest j * p ^ i is less than N, the rest of the species fall out of the wash, For example, in In our example p = 3 we get 4 p contributed by product 1-9, another 4 contributed by product 10-18, and another one capable of 21. These first two are simply a multiple of p ^ 2; f (2) = 4 tells us that every multiple p ^ 2 contributes another 4 p to the product.
[update]
The code always helps clarify. Save the following perl script as foo.pl and run it as foo.pl <p> <k> . Note that ** is the Perl exponent operator, bdiv computes the factor and remainder for BigInts (integers with unlimited precision), and use bigint tells Perl to use BigInts everywhere.
#!/usr/bin/env perl use warnings; use strict; use bigint; @ARGV == 2 or die "Usage: $0 <p> <k>\n"; my ($p, $k) = map { Math::BigInt->new($_) } @ARGV; sub f { my $i = shift; return ($p ** $i - 1) / ($p - 1); } my $j = 0; while (f($j) <= $k) { $j++; } $j--; my $N = 0; my $r = $k; while ($r > 0) { my $val = f($j); my ($q, $new_r) = $r->bdiv($val); $N += $q * ($p ** $j); $r = $new_r; $j--; } print "Result: $N\n"; exit 0;