Number of +ve integers that have n as their greatest prime power

hv at crypt.org hv at crypt.org
Mon Dec 13 15:32:22 CET 2004


While trying to refine a program to deliver guaranteed minimal values
for the previously discussed "sum of unit fractions" email I stumbled
on the following sequence, which seems reasonably interesting:

%I A000001
%S A000001 1,1,2,2,6,0,12,8,16,0,48,0,96,0,0,48,240,0,480,0,0,0,960,0,960,0
%T A000001 960,0,3840,0,7680,3072,0,0,0,0,18432,0,0,0,36864,0,73728,0,0,0
%U A000001 147456,0,147456,0,0,0,442368,0,0,0,0,0,884736,0,1769472,0,0,589824
%N A000001 For each prime power n, a(n) is the number of positive integers that have n as their greatest prime power.
%e A000001 a(4) = 2 since only 4 and 12 have 4 as their greatest prime power - all other multiples of 4 are divisible by 8, 9, or some prime >= 5.
%F A000001 a(1) = 1; a(p^k) = prod_{q <= p^k, q prime} { floor(k ln p / ln q) } / k when p prime, k >= 1, a(n) = 0 otherwise
%C A000001 a(n) is the number of occurrences of n in A034699
%K A000001 nonn,easy,new
%O A000001 1,3
%Y A000001 Cf A034699
%A A000001 hv at crypt.org (Hugo van der Sanden)

Can someone confirm that the formula is correct, and perhaps check that
my numbers are correct?

Hugo





More information about the SeqFan mailing list