#A4 INTEGERS 24 (2024)

ALGORITHMS AND BOUNDS ON THE SUMS OF POWERS OF

CONSECUTIVE PRIMES

Cathal O’Sullivan1
Department of Mathematics, Statistics, and Actuarial Science, and Department of
Computer Science and Software Engineering, Butler University, Indianapolis,
Indiana

Jonathan P. Sorenson
Department of Computer Science and Softare Engineering, Butler University,
Indianapolis, Indiana
[email protected]

Aryn Stahl2
Department of Physics and Astronomy, and Department of Computer Science and
Software Engineering, Butler University, Indianapolis, Indiana

Received: 6/1/23, Accepted: 12/15/23, Published: 1/2/24

Abstract
For an integer k > 1, let sk (x) count the number of representations of integers
n ≤ x as the sum of kth powers of consecutive primes. We present and analyze an
algorithm to enumerate all such integers n and an algorithm to compute the value of
sk (x). We also present asymptotic upper and lower bounds on sk (x) that are within
a constant factor of one another. In particular, we show that sk (x) ∼ x2/(k+1)+o(1) .
This work extends previous work by Tongsomporn, Wananiyakul, and Steuding
(2022) who examined sums of squares of consecutive primes.

1. Introduction

Let Sk (x) denote the set of integers n ≤ x that can be written as a sum of the kth
powers of consecutive primes. For example, 53 + 73 + 113 = 1799 is an element of
S3 (2000). Let sk (x) be the number of such n, counted with multiplicity. If a specific
integer n has more than one representation as the sum of kth powers of consecutive
primes, we count all such representations when we say ”with multiplicity”. So we
have sk (x) ≥ #Sk (x).
DOI: 10.5281/zenodo.10450932
1 Current affiliation: AbbVie, Lake Bluff, Illinois
2 Current affiliation: Naval Surface Warfare Center, Crane, Indiana
INTEGERS: 24 (2024) 2

In this paper, we describe an algorithm that, given k and x, produces the elements
of Sk (x) along with their representation. Its running time is linear in sk (x), the
number of such representations. The algorithm uses O(kx1/k ) space. This is Section
2. In Section 3, we describe a second algorithm that computes the value of sk (x),
with multiplicity, given k and x. This algorithm takes O(x1/k / log log x) arithmetic
operations, the time it takes to find all primes up to x1/k . In Section 4 we show
that
x2/(k+1)
sk (x) ≤ (1 + o(1)) · ck ,
(log x)2k/(k+1)
where ck = (k 2 /(k − 1)) · (k + 1)1−1/k . This is a generalization of a bound for s2 (x)
proven in [6]. Their bound is explicit and ours is not. This is also an upper bound
on the number of arithmetic operations used by our enumeration algorithm. Also
in Section 4, we give the lower bound

(k + 1)2 x2/(k+1)
sk (x) ≥ (1 + o(1)) · ,
2 (log x)2k/(k+1)

In Section 5 we apply our new algorithm to compute Sk (x) for various x and k, and
give some examples of integers that can be written as sums of consecutive powers
of primes in more than one way. Note that S2 (5000) was computed by [6]; see also
sequence A340771 at the On-Line Encyclopedia of Integer Sequences [1].
We begin by describing our enumeration algorithm in the next section.

2. The Enumeration Algorithm

Given as input a bound x and integer exponent k > 1, our algorithm produces the
elements of the set Sk (x) as follows.
Let p1 = 2, p2 = 3, . . . denote the primes, and let π(y) denote the number of
primes less than or equal to y. By the Prime Number Theorem (see, for example,
[4]), π(y) ∼ y/ log y, and thus p` ∼ ` log `.
We assume all arithmetic operations take constant time. In practice, all our
integers are at most 128 bits, or roughly 38 decimal digits.
The three steps of our algorithm are as follows:

1. Find the primes up to x1/k .

2. Compute the prefix sum array f [ ], where f [0] = 0 and f [i] := pk1 +pk2 +· · ·+pki
for all i ≤ π(x1/k ), so that f [i + 1] = f [i] + pki+1 .

3. Loops to enumerate Sk (x):

for b := 0 to π(x1/k ) − 1 do:

INTEGERS: 24 (2024) 3

for t := b + 1 to π(x1/k ) do:

n := f [t] − f [b];
if n > x break the t loop,
else output(n, pb+1 );

Remark 1. Step 1 is not the bottleneck, so the Sieve of Eratosthenes is sufficient,

taking O(x1/k log log x) time. See also [2, 5]. Note that in the second step, the value
of the largest entry in the array is bounded by x1+1/k . If we use a binary algorithm
for integer exponentiation, Step 2 takes time O(π(x1/k ) log k), which is smaller than
the asymptotic bound given for Step 1. Storing f [ ] uses O(kx1/k ) bits of space. The
time for Step 3 is proportional to the number of (n, pb+1 ) pairs that are output,
which is sk (x). This, in turn, we bound asymptotically in Theorem 1 below, at
ck x2/(k+1) /(log x)2k/(k+1) time. We output pairs (n, pb+1 ) in case a specific value of
n gets repeated. If we have repeats for n, the pb+1 values will be different, and pb+1
is the first prime in the sequence of powers of primes to generate n, allowing us to
quickly reconstruct two (or more) representations of n as kth powers of consecutive
primes. In practice, we found repeated values of n to be quite rare.

Example 1. Let us compute S3 (1000).

1. We find the primes up to 10001/3 = 10, so 2, 3, 5, 7.

2. We compute the prefix array f [ ] as follows:

0 1 2 3 4
0 8 35 160 503

3. We generate the f [t] − f [b] values, and hence S3 (1000), as follows:

b=0: (8, 2), (35, 2), (160, 2), (503, 2)

b=1: (27, 3), (152, 3), (495, 3)
b=2: (125, 5), (468, 5)
b=3: (343, 7)

And thus s3 (1000) = 10.

3. A Counting Algorithm

In this section we describe an algorithm that computes sk (x), with multiplicity.

Since we are not explicitly constructing all the representations of the integers, we
are able to save a considerable amount of time by collapsing the inner loop in Step
3 of the previous algorithm.

1. Find the primes up to x1/k .

INTEGERS: 24 (2024) 4

2. Compute the prefix sum array f [ ] as done above.

3. Loop to compute the count:

count := 0; t := 0;
while(t < π(x1/k ) and f [t + 1] ≤ x) do:
t := t + 1;
for b := 0 to π(x1/k ) − 1 do:
if t < π(x1/k ) and f [t + 1] − f [b] ≤ x then
t := t + 1;
count := count + (t − b);

It is easy to see that the running time for the last step is O(π(x1/k )) arithmetic oper-
ations. So finding the primes in Step 1 dominates the running time, at O(x1/k / log log x)
time using, say, the Atkin-Bernstein prime sieve [2].

4. Analysis

In this section we prove the following theorem, which provides an upper bound on
sk (x).

Theorem 1. For k > 1 we have

x2/(k+1)
sk (x) ≤ (1 + o(1)) · ck ,
(log x)2k/(k+1)

where ck = (k 2 /(k − 1)) · (k + 1)1−1/k .

Note that ck ∼ k 2 for large k. In [6] the authors prove the explicit bound

x2/3
s2 (x) ≤ 28.4201 .
(log x)4/3

We also have the trivial lower bound sk (x) ≥ π(x1/k ) ∼ kx1/k / log x by the Prime
Number Theorem.
Our proof follows the same lines as in [6]. We begin by partitioning the members
of Sk (x) by the number of prime powers m in their representative sum. Define

sk,m (x) = #{n ≤ x : there exists ` ≥ 0 : n = pk`+1 + · · · + pk`+m }

PM
so that sk (x) = m=1 sk,m (x) for a sufficiently large, and as yet unknown value
M = M (x, k), the length of the longest sum of powers of consecutive primes less
that or equal to x.
INTEGERS: 24 (2024) 5

Lemma 1 ([6]). For k > 1 and m > 0 we have

sk,m (x) ≤ π((x/m)1/k ).

Proof. Let ` = sk,m (x). We have

mpk` ≤ pk` + pk`+1 + · · · + pk`+(m−1) ≤ x.

Thus mpk` ≤ x, or p` ≤ (x/m)1/k , or sk,m (x) = ` ≤ π((x/m)1/k ).

Next, we need an estimate for M .

Lemma 2. For k > 1 we have

x1/(k+1)
M (x, k) ∼ (k + 1) .
(log x)k/(k+1)

Proof. We have
M
X M
X +1
pk` ≤ x < pk` .
`=1 `=1

Using the asymptotic estimate pM ∼ M log M from the Prime Number Theorem
and using the methods from [3, Section 2.7] we have
M
X X Z M log M
pk` ∼ pk = tk dπ(t)
`=1 p≤M log M 2

M log M M log M
tk
Z Z
1
∼ dt ∼ tk dt,
2 log t log M 2

and so we have
(M log M )k+1
x∼ .
(k + 1) log M
Taking the logarithm of both sides gives us (k + 1) log M ∼ log x. We then obtain
that
M ∼ (k + 1)(x log x)1/(k+1) / log x.

We are now ready to prove Theorem 1.

Proof. We have
M
X M
X
sk (x) = sk,m (x) ≤ π((x/m)1/k ).
m=1 m=1
INTEGERS: 24 (2024) 6

By the Prime Number Theorem and our lemmas, we have

M
X M
X
sk (x) ≤ π((x/m)1/k ) ∼ k(x/m)1/k / log(x/m)
m=1 m=1
M
1/k X
kx kx1/k M 1−1/k
∼ m−1/k ∼ .
log x m=1
log x 1 − 1/k

Plugging in our estimate for M from Lemma 2 gives this bound for sk (x):
1−1/k
kx1/k k x1/(k+1)

(k + 1) .
log x k − 1 (log x)k/(k+1)

A bit of algebra simplifies the exponents to complete the proof.

Note that limk→∞ (1/k) · (k + 1)1−1/k = 1.

We wrap up this section with our lower bound proof for sk (x).

Theorem 2. For k > 1 we have

(k + 1)2 x2/(k+1)
 
M
sk (x) ≥ ≥ (1 + o(1)) · .
2 2 (log x)2k/(k+1)

Proof. Consider the sum pk1 + · · · + pkM , which is at most x by definition. The
lower bound
is obtained by counting the number of i, j pairs with 1 ≤ i ≤ j ≤ M ,
which is M k k
2 , as each sum pi + · · · + pj gives an integer n counted by sk (x). Thus,
sk (x) ≥ M (M − 1)/2, and apply Lemma 2.

5. Empirical Results

In this section we give some of our empirical results. This is not everything we have
– the interested reader is encouraged to contact the second author for copies of the
data or source code.

5.1. Tightness of Theorems 1 and 2

In Tables 1–5, we present values of sk (x) for k = 2, 3, 5, 10, 20 for x up to 1038 ,
which is close to the limit for 128-bit hardware integer arithmetic. We also include
the upper bound from Theorem 1 and the lower bound from Theorem 2.
Following the tables, we have graphed our upper bound (green) and lower bound
(blue) estimates with the exact counts (purple) from Tables 1–5 to show how tight
our bounds are in practice. In our graph for k = 2 we also include the explicit upper
bound (orange) from [6].
INTEGERS: 24 (2024) 7

x s2 (x) Upper Lower

103 37 52 34
104 132 166 108
105 519 574 372
106 1998 2089 1357
107 7840 7898 5130
108 31372 30681 19928
109 126689 121714 79056
1010 517191 490907 318853
1011 2132474 2006670 1303370
1012 8867094 8293885 5387036
1013 37153225 34599930 22473314
1014 156713533 145488607 94497622
1015 665005737 615948906 400070550

Table 1: Values of s2 (x), with upper and lower bounds

x s3 (x) Upper Lower

103 10 19 13
104 29 40 28
105 70 91 64
106 186 220 155
107 491 554 390
108 1297 1434 1011
109 3501 3801 2681
1010 9568 10262 7240
1011 26429 28130 19846
1012 73575 78071 55080
1013 206617 218951 154472
1014 584184 619541 437093
1015 1663904 1766547 1246320
1016 4769563 5070868 3577556
1017 13742399 14641613 10329827
1018 39796129 42496537 29981799
1019 115807012 123917289 87425082
1020 338386013 362841801 255989092

Table 2: Values of s3 (x), with upper and lower bounds

INTEGERS: 24 (2024) 8

x s10 (x) Upper Lower

x s5 (x) Upper Lower
1010 10 21 13
105 10 20 14
1011 15 26 16
106 21 32 22
1012 21 35 22
107 38 54 37
1013 36 45 28
108 68 94 65
1014 45 61 38
109 127 167 115
1015 56 81 51
1010 243 302 208
1016 78 110 69
1011 479 556 382
1017 120 150 94
1012 862 1037 712
1018 154 206 129
1013 1639 1956 1343
1019 214 284 178
1014 3128 3725 2558
1020 301 393 247
1015 6053 7154 4913
1021 439 547 344
1016 11799 13841 9507
1022 599 765 481
1017 22938 26954 18513
1023 832 1072 674
1018 44869 52794 36262
1024 1187 1508 949
1019 87959 103940 71393
1025 1678 2129 1339
1020 173621 205585 141209
1026 2373 3013 1895
1021 343199 408328 280466
1027 3304 4276 2690
1022 681611 814086 559167
1028 4817 6083 3827
1023 1359330 1628652 1118664
1029 6786 8674 5457
1024 2717318 3268557 2245058
1030 9744 12396 7799
1025 5451410 6578721 4518694
1031 13788 17751 11168
1026 10962586 13276572 9119214
1032 19871 25467 16022
1027 22107170 26859747 18449024
1033 28290 36601 23027
1028 44656828 54464244 37409592
1034 40949 52692 33150
1029 90459929 110673813 76017986
1035 58459 75976 47799
1030 183613129 225340599 154778606
1036 84393 109711 69023
1031 373421607 459662117 315725893
1037 121302 158647 99810
1032 761023562 939272425 645153503
1038 175797 229717 144523

Table 3: Values of s5 (x), with upper Table 4: Values of s10 (x), with upper
and lower bounds and lower bounds
INTEGERS: 24 (2024) 9

x s20 (x) Upper Lower

1020 10 20 12
1021 15 23 13
1022 15 26 15
1023 21 30 17
1024 21 35 20
1025 28 40 23
1026 36 46 27
1027 36 54 31
1028 45 63 36
1029 45 73 42
1030 66 85 49
1031 66 100 58
1032 78 117 68
1033 105 138 80
1034 120 162 94
1035 136 191 111
1036 171 225 131
1037 190 266 154
1038 232 315 183

Table 5: Values of s20 (x), with upper and lower bounds

Figure 1: Graph of Table 1

INTEGERS: 24 (2024) 10

Figure 2: Graph of Table 2

Figure 3: Graph of Table 3

INTEGERS: 24 (2024) 11

Figure 4: Graph of Table 4

Figure 5: Graph of Table 5

INTEGERS: 24 (2024) 12

We conclude this subsection with a comparison of the constants ck from Theorem

1 with the value of (k + 1)2 /2 from Theorem 2.
k ck (k + 1)2 /2
2 6.92 4.5
3 11.33 8.0
4 17.83 12.5
5 26.21 18.0
6 36.44 24.5
7 48.54 32.0
8 62.52 40.5
9 78.39 50.0
10 96.16 60.5
11 115.84 72.0
12 137.43 84.5
13 160.94 98.0
14 186.38 112.5
15 213.75 128.0
16 243.05 144.5
17 274.29 162.0
18 307.47 180.5
19 342.60 200.0
20 379.68 220.5

5.2. Duplicates
We found 40 values of n ≤ x = 1012 that have multiple representations as sums of
consecutive squares of primes. The smallest such number is 14720439, which can
be written as

9412 + 9472 + 9532 + 9672 + 9712 + 9772 + 9832 + 9912 + 9972 + 10092 +
10132 + 10192 + 10212 + 10312 + 10332

and as

1312 + 1372 + 1392 + 1492 + 1512 + 1572 + 1632 + 1672 + 1732 + 1792 +
1812 +1912 +1932 +1972 +1992 +2112 +2232 +2272 +2292 +2332 +2392 +
2412 +2512 +2572 +2632 +2692 +2712 +2772 +2812 +2832 +2932 +3072 +
3112 +3132 +3172 +3312 +3372 +3472 +3492 +3532 +3592 +3672 +3732 +
3792 +3832 +3892 +3972 +4012 +4092 +4192 +4212 +4312 +4332 +4392 +
4432 +4492 +4572 +4612 +4632 +4672 +4792 +4872 +4912 +4992 +5032 +
5092 +5212 +5232 +5412 +5472 +5572 +5632 +5692 +5712 +5772 +5872 +
5932 +5992 +6012 +6072 +6132 +6172 +6192 +6312 +6412 +6432 +6472 .

To find these, we sorted the output of our algorithm from Section 2, and then used
the uniq -D unix/linux command to list the duplicates.
We found no integers that can be written as the sum of consecutive powers of
primes in more than one way for any power larger than 2. We searched for cubes up
to 1018 , fifth powers up to 1027 , and tenth and twentieth powers up to 1038 . This
INTEGERS: 24 (2024) 13

n Prime 1 Prime 2 n Prime 1 Prime 2

14720439 131 941 47638558043 28097 65731
16535628 1123 569 50195886916 479 6857
34714710 2389 401 50811319931 2039 21283
40741208 131 653 56449248367 2803 4127
61436388 569 809 86659250142 4561 53609
603346308 401 919 105146546059 29587 6599
1172360113 3701 4673 119789313426 31847 42299
1368156941 1367 16519 125958414196 16763 26183
1574100889 3623 613 134051910100 183047 4397
1924496102 11657 2803 159625748030 1367 3301
1989253499 3359 613 169046403821 183829 19717
2021860243 3701 4297 263787548443 47297 62347
6774546339 11273 47513 330881994258 11161 2039
9770541610 1663 7243 438882621700 16763 20369
12230855963 10177 2777 507397251905 643 75013
12311606487 28603 3257 572522061248 18427 44371
12540842446 11087 479 687481319598 16139 338461
14513723777 1663 6323 780455791261 3257 7057
26423329489 1709 32401 847632329089 184003 7523
38648724198 2777 6967 854350226239 14821 6599

Table 6: Duplicates for k = 2

search requires computing Sk (x) and not just sk (x); note that it is much faster to
compute just sk (x) in practice because outputting the elements of Sk (x) to a text
file slows down the computation considerably.
We found exactly one example with differing powers:

23939 = 232 + 292 + 312 + 372 + 412 + 432 + 472 + 532 + 592 + 612 + 672
= 173 + 193 + 233 .

We conclude this subsection with the list of 40 integers up to 1012 that can be
written as sums of squares of consecutive primes in two ways. For each such integer
in the Table 6, we list the starting primes for each of their two ways to sum.

5.3. Initial Elements of Sk

We wrap up the presentation of our computations with the first few elements of
each of the Sk sets we computed. We have the following:
S2 : 4 9 13 25 34 38 49 74 83 87 121 169 170 195 204 208 289 290 339 361;
S3 : 8 27 35 125 152 160 343 468 495 503 1331 1674 1799 1826 1834 2197 3528
3871 3996 4023;
S5 : 32 243 275 3125 3368 3400 16807 19932 20175 20207 161051 177858 180983
181226 181258 371293 532344 549151 552276 552519;
S10 : 1024 59049 60073 9765625 9824674 9825698 282475249 292240874 292299923
292300947;
INTEGERS: 24 (2024) 14

S20 : 1048576 3486784401 3487832977 95367431640625 95370918425026

95370919473602 79792266297612001 79887633729252626 79887637216037027
79887637217085603.

6. Future Work

We have several ideas for future work:

Our primary goal is to parallelize our algorithm from Section 2 to extend our
computations. For larger powers, this will also mean using multiple-precision integer
arithmetic using, for example, GMP.
More careful proofs of Theorems 1 and 2 might give explicit bounds, or perhaps
an asymptotic constant. If such a constant exists, it appears to be near 0.6.
Is there a power k > 2 for which there are integers with multiple representations
as sums of powers of consecutive primes? We have not found any as of yet.

Acknowledgements. The authors are grateful to Frank Levinson for his support of
computing research infrastructure at Butler University. The first and third authors
were Butler University undergraduates at the time this work was done.

References
[1] The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

[2] A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp.
73 (2004), 1023–1030, URL http://cr.yp.to/papers.html#primesieves.

[3] E. Bach and J. O. Shallit, Algorithmic Number Theory, vol. 1, MIT Press, Cambridge Mas-
sachusetts, 1996.

[4] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University
Press, Oxford, 5th edn., 1979.

[5] J. P. Sorenson, Two compact incremental prime sieves, LMS J. Comput. Math. 18 (2015),
675–683, URL http://journals.cambridge.org/article S1461157015000194.

[6] J. Tongsomporn, S. Wananiyakul, and J. Steuding, Sums of consecutive prime squares, Integers
22 (2022), #A9.