cp's OEIS Frontend

A336825 a(n) is the smallest positive integer which is expressed by the greedy algorithm as the sum of exactly n prime-powers (including 1).

%I A336825 #23 Aug 06 2020 00:36:23
%S A336825 1,6,95,360748
%N A336825 a(n) is the smallest positive integer which is expressed by the greedy algorithm as the sum of exactly n prime-powers (including 1).
%C A336825 Analogous to A066352 with prime-powers replacing primes.
%H A336825 Steven and Jonathan Hoseana, <a href="https://arxiv.org/abs/2008.01368">The prime-power map</a>, arXiv:2008.01368 [math.DS], 2020.
%F A336825 a(1) = 1 and, for every positive integer n, a(n+1) = a(n) + q1(n), where (q1(n), q2(n)) is the first pair of consecutive prime-powers with q2(n) - q1(n) >= a(n) + 1.
%e A336825 The greedy algorithm expresses every positive integer as a sum of prime-powers (including 1) by choosing the largest possible summand at each step. Consider the following initial data of such expressions:
%e A336825 1 = 1,
%e A336825 2 = 2,
%e A336825 3 = 3,
%e A336825 4 = 4,
%e A336825 5 = 5,
%e A336825 6 = 5 + 1,
%e A336825 7 = 7,
%e A336825 8 = 7 + 1,
%e A336825 9 = 9,
%e A336825 10 = 9 + 1.
%e A336825 The smallest positive integer which is expressed by the greedy algorithm as the sum of exactly 1 prime-power is a(1) = 1. The smallest positive integer which is expressed by the greedy algorithm as the sum of exactly 2 prime-powers is a(2) = 6. Similarly, a(3) = 95 (95 = 89 + 5 + 1) and a(4) = 360748 (360748 = 360653 + 89 + 5 + 1).
%o A336825 (PARI) ispp(n) = isprimepower(n) || (n==1); \\ A000961
%o A336825 f(n) = while(!ispp(n), n--); n; \\ A031218
%o A336825 nbs(n) = my(nb=0); while(n, n -= f(n); nb++); nb;
%o A336825 a(n) = my(k=1); while (nbs(k) != n, k++); k; \\ _Michel Marcus_, Aug 05 2020
%Y A336825 Cf. A066352, A000961 (power of primes), A031218.
%K A336825 nonn,more
%O A336825 1,2
%A A336825 _Jonathan Hoseana_, Aug 04 2020