Algorithms for Complementary Sequences

#A95 INTEGERS 25 (2025)
ALGORITHMS FOR COMPLEMENTARY SEQUENCES
Chai Wah Wu
Ma hema ics o Compu a ion, IBM Resea ch, T. J. Wa son Resea ch Cen e ,
Yo k own Heigh s, New Yo k
[email p o ec ed]
Recei ed: 9/9/24, Accep ed: 9/30/25, Published: 11/5/25
Abs ac
Finding he n- h posi i e squa e numbe is easy, as i is simply n2. Bu how do
we ind he complemen a y sequence, i.e., he n- h posi i e non-squa e numbe ?
Fo his case he e is an explici o mula. Howe e , o gene al cons ain s on
numbe s, a o mula is ha de o ind. In his pape , we s udy how o compu e he
n- h in ege ha does (o does no ) sa is y a ce ain condi ion. In pa icula , we
conside i as a ixed poin p oblem, ela e i o he i e a i e me hod o Lambek
and Mose , s udy a bisec ion app oach o his p oblem, and p o ide no el o mulas
o a ious complemen a y sequences including he non-k-gonal numbe s, non-k-
gonal-py amidal numbe s, non-k-simplex numbe s, non-sum-o -k- h-powe s, non-k-
h-powe s, and non-Jacobs hal numbe s.
1. In oduc ion
Fo a posi i e in ege n∈N+, he n- h posi i e squa e numbe is simply n2. Can
we also easily ind he complemen a y sequence? In o he wo ds, wha is he n- h
posi i e non-squa e numbe ? I is qui e ema kable ha he e exis s an explici
o mula o he n- h posi i e non-squa e numbe : n+⌊1
2+√n⌋=n+⌊pn+⌊√n⌋⌋
[9,13,15,16]. This can also be compu ed as n+⌊√n⌋+ 1 i n > ⌊√n⌋(⌊√n⌋+ 1)
and as n+⌊√n⌋o he wise. These o mulas a e well-sui ed o implemen a ion in
a compu e algo i hm since many compu e languages and numbe heo y so wa e
packages include unc ions o compu e ⌊√n⌋. Fo ins ance, he isq unc ion in
Py hon, Julia, and Maple all pe o m his calcula ion. These o mulas ha e been
ex ended o highe powe s as well. In pa icula , he n- h non-k- h-powe numbe
is gi en by n+⌊k
pn+⌊k
√n⌋⌋ [13,17,22].1
DOI: 10.5281/zenodo.17535229
1The compu a ion o ⌊k
√n⌋ o a bi a y in ege s kand n≥0 is eadily a ailable in symbolic
compu e algeb a sys ems and so wa e o numbe heo y. Fo ins ance, ⌊k
√n⌋can be compu ed
wi h he in ege _n h oo unc ion in he sympy Py hon module which in u n uses he mpz_ oo
unc ion in he mul iple p ecision lib a y gmp. Al hough hese compu e ope a ions assume ha
INTEGERS: 25 (2025) 2
Fo Pa logical s a emen on he na u al numbe s, le us de ine P(n) as he
n- h posi i e na u al numbe msuch ha P(m) is ue. Fo he case whe e P(m)
deno es he logical s a emen “mis squa e”, P(n) is easily de e mined, since he
lis o in ege s msuch ha P(m) is ue a e easily enume a ed. As no ed in he
example abo e, o his pa icula P, he unc ion ¬P(n) can also be compu ed
by an explici o mula. Howe e , in gene al, he simplici y o Pdoes no imply
he simplici y o ¬P. Fu he mo e, o mo e gene al s a emen s P, he o mula o
P(n) o ¬P(n) may no be eadily a ailable. E en i such explici o mulas a e
a ailable, some o hem equi e he use o loa ing poin a i hme ic and i can be
di icul o use compu a ionally o ind P(n) o ¬P(n), especially o la ge n. See
o example he o mulas o he n- h non-Fibonacci numbe in [4,5] which equi e
logϕa high p ecision o la ge n. While he e ha e been many s udies o explici
o mulas o such complemen a y sequences [4,5,9,13,15–17,22], he e ha e no been
much s udy in compu e algo i hms o calcula e such sequences. The pu pose o
his pape is o discuss algo i hms o compu e P(n) o ¬P(n). As a consequence,
we show ha he n- h non-k-gonal numbe is gi en by n+$ 2n−2+⌊k+1
4⌋
k−2+1
2%
and ha he n- h non-second-hexagonal numbe is n+pn
2−1.
2. Finding P(n) as he Solu ion o a Fixed Poin P oblem
Fo an in ege a, de ine he coun ing unc ion CP(a) = |{b∈N: (1 ≤b≤a)∧P(b)}|
as he numbe o posi i e in ege s less han o equal o asuch ha P(a) is ue. I
is clea ha CP(a) is inc easing, 0 ≤CP(a)≤a, and 0 ≤C¬P(a) = a−CP(a)≤a.
Fu he mo e, P(n) is he smalles in ege msuch ha CP(m) = n. Also no e ha
Pis s ic ly inc easing and P(n)≥n.
De ine gn(x) = n+C¬P(x) = n+x−CP(x). A ixed poin xo gnsa is ies
x=n+x−CP(x), i.e., CP(x) = n. Thus, he smalles ixed poin o gnis equal o
P(n). Fu he mo e, a ixed poin o gn ha is in he ange o Pis equal o P(n).
In pa icula , i gnhas a unique ixed poin , hen i mus necessa ily be equal o
P(n). Finding a ixed poin o (x) is equi alen o inding a oo o (x)−x.
Equi alen ly, we could de ine ˜gn(x) = n−CP(x) and ind he oo s o ˜gn. Howe e ,
in he sequel we will conside he ixed poin o mula ion as gnis de ined wi h C¬P
and has a mo e na u al in e p e a ion o complemen a y sequences. Fu he mo e,
we show below ha he unc ion i e a ion me hod sol ing his ixed poin p oblem
is equi alen o he well-known Lambek-Mose me hod o de ining complemen a y
sequences.
The unc ion gn, iewed as a unc ion on he eal numbe s, is a piecewise-linea
nis an in ege , hey can be used o compu e ⌊k
√n⌋ o all eal n≥0 since ⌊k
√n⌋=⌊k
p⌊n⌋⌋ o
n≥0 (see [6, Equa ion 3.9]).
INTEGERS: 25 (2025) 3
unc ion. Fo each alue o n, he unc ion gncoincides wi h he iden i y unc ion
on he segmen spanned by {m∈N:CP(m) = n}. I is clea ha gn(m)> m i
m < P(n) and gn(m)≤m o m≥ P(n). As an example, we show in Figu e 1
he unc ion gn o he case whe e P(m) deno es he s a emen “mis p ime” and
nis equal o 4. No ice ha he minimal ixed poin is a x= 7 which co esponds
o P(4), i.e., he ou h p ime numbe . Nex , le us conside me hods o ind
he smalles ixed poin o such an inc easing piecewise-linea unc ion gnon he
in ege s.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
g
4(
x
)
Figu e 1: gn(x) when n= 4 and P(m) deno e he logical s a emen “mis p ime”.
The minimal ixed poin is a x= 7 which co esponds o P(4), he ou h p ime
numbe .
2.1. Func ion I e a ion Me hod
The unc ion i e a ion me hod o ind a ixed poin o a unc ion is a classical
me hod ha da es back o a leas He on’s me hod o inding an app oxima ion
o he squa e oo [7] and is used in gene al oo inding algo i hms. We i s pick
an ini ial condi ion less han o equal o P(n). Since n≤ P(n), we can s a
INTEGERS: 25 (2025) 4
wi h he ini ial condi ion x=nand apply he i e a ion x→gn(x) epea edly un il
con e gence (Algo i hm 1). This is o example implemen ed in he FixedPoin
unc ion in Ma hema ica. No e ha since gn(x)≥xini ially, a each s ep o he
algo i hm he alue o xinc eases, un il i eaches a poin whe e gnin e sec s wi h
he iden i y unc ion, which is he smalles ixed poin , i.e., P(n). Fo he ini ial
condi ion x=n, i is easy o see ha his me hod is equi alen o he Lambek-Mose
me hod and [13] showed ha i indeed con e ges o he smalles ixed poin .
Algo i hm 1 Func ion i e a ion me hod on gn(x) o compu e P(n).
Requi e: gn(x)▷compu es he minimal ixed poin o gn.
m←n
while gn(m)=mdo
m←gn(m)
end while
e u n m
While he Lambek-Mose me hod assumes he ini ial condi ion x=n, depending
on Pwe may choose a mo e sui able ini ial condi ion. Fo ins ance, i P(m) deno es
he s a emen “mis he p oduc o kdis inc p imes”, hen he ini ial condi ion
can be chosen as max(n, pk#) since P(n)≥pk# whe e pk# is he k- h p imo ial.
The numbe o s eps needed o con e gence is less han P(n)−nand hus
his algo i hm is e icien when P(n)−nis small wi h espec o n, i.e., when
he numbe s sa is ying Pa e dense. In pa icula , in [13] i is shown ha i he
di e ence unc ion o ¬Phas a leas a linea g ow h a e (implying ha ¬Pg ows
a leas quad a ically) hen 2 s eps su ice. Mo e p ecisely, he ollowing esul is
shown.
Theo em 1. I ¬P(m+ 1) − ¬P(m)≥m o all m, hen
P(n) = gn(gn(n)) = n+C¬P(n+C¬P(n)).
Sequences sa is ying hese condi ions include non-k- h-powe s o he non-powe s
o k. Thus, in hese cases he compu a ion o P(n) equi es a mos 2 e alua ions
o he coun ing unc ion C¬P. We nex show ha 1 e alua ion su ices.
Theo em 2. I ¬P(m+ 1) − ¬P(m)≥m o all m, hen
P(n) = (n+C¬P(n)+1 i n+C¬P(n)≥ ¬P(C¬P(n) + 1)
n+C¬P(n)o he wise.
P oo . Fi s no e ha ¬P(C¬P(n) + 1) > n. By hypo hesis,
¬P(C¬P(n) + 2) ≥C¬P(n) + 1 + ¬P(C¬P(n) + 1) > C¬P(n) + n=gn(n).
INTEGERS: 25 (2025) 5
This means ha C¬P(n)+2> C¬P(C¬P(n) + n) = gn(gn(n)) −n, i.e.,
gn(gn(n)) < n +C¬P(n)+2.
Since C¬Pis inc easing, gn(gn(n)) ≥n+C¬P(n). Finally, i is easy o see ha he
h eshold whe e gn(gn(n)) changes om n+C¬P(n) o n+C¬P(n) + 1 is p ecisely
gi en by n+C¬P(n)≥ ¬P(C¬P(n) + 1).
This can be mo e compac ly exp essed using he I e son b acke [10,12], which
we deno e using JK:
P(n) = n+C¬P(n) + Jn+C¬P(n)≥ ¬P(C¬P(n) + 1)K.
Nex we show se e al applica ions o Theo em 2.
2.1.1. Non-k- h-powe s
As an example o applying Theo em 2, we gi e he ollowing o mula o he n-
h non-k- h powe o k > 1, which simpli ies he o mula gi en in Sec ion 1by
equi ing only one e alua ion o he in ege k- h oo unc ion ⌊k
√n⌋:
a(n) = (n+⌊k
√n⌋+ 1 i n+⌊k
√n⌋ ≥ (⌊k
√n⌋+ 1)k
n+⌊k
√n⌋o he wise.
2.1.2. Non-Me senne Numbe s
Simila ly, o he non-Me senne numbe s (i.e., numbe s no o he o m 2p−1 o p
p ime), we ha e o n > 1 he o mula
a(n) = n+s+ 1 i n+1+s≥2ps+1
n+so he wise,
whe e s=⌊log2π(n)⌋,pkis he k- h p ime, and π(n) is he p ime coun ing unc ion
ha e u ns he numbe o p ime numbe s less han o equal o n.
2.1.3. Non-Fe ma Numbe s
The Fe ma numbe s a e de ined as 22n−1+ 1 o n≥1, i.e., 3,5,17,257,65537, . . ..
The i s wo non-Fe ma numbe s a e 1 and 2 and he n- h non-Fe ma numbe s
o n > 2 a e
a(n) = (n+⌊log2(log2(n−1))⌋+ 2 i n+⌊log2(log2(n−1))⌋ ≥ 42⌊log2(log2(n−1))⌋
n+⌊log2(log2(n−1))⌋+ 1 o he wise.

INTEGERS: 25 (2025) 6
2.1.4. Non-powe s o k
Simila ly, o he non-powe s o kwe ha e he o mula
a(n) = (n+1+⌊logkn⌋+ 1 i n+1+⌊logkn⌋ ≥ k⌊logkn⌋+1
n+1+⌊logkn⌋o he wise.
2.1.5. Non-Jacobs hal Numbe s
The Jacobs hal numbe s 0,1,1,3,5,11,21, . . . a e de ined ecu si ely as he sequence
a(n) = n o n≤1 and a(n) = a(n−1)+2a(n−2) o he wise. I can also be de ined
as he nea es in ege o 2n
3. This sequence is sequence A001045 o he on-line ency-
clopedia o in ege sequences (OEIS) [19]. Looking only a he posi i e in ege s and
igno ing he duplica e 1, we ob ain he sequence 1,3,5,11,21, . . . whose de ini ion
can be w i en as ¬P(n) = j2n+1+1
3k. The numbe o such numbe s less han o
equal o nis 1,1,2,2,3, ... which can be w i en as C¬P(n) = ⌊log2(3n+ 1)⌋ − 1.
Applying his o Theo em 2 esul s in he ollowing o mula o he non-Jacobs hal
numbe s (OEIS A147613):
a(n) = (n+⌊log2(3n+ 1)⌋i n+⌊log2(3n+ 1)⌋>j2⌊log2(3n+1)⌋+1+1
3k
n+⌊log2(3n+ 1)⌋−1 o he wise.
(1)
No e ha ⌊log2(x)⌋+1 is equal o he numbe o bi s in he bina y ep esen a ion
o he in ege xand his quan i y is easily a ailable in many p og amming languages.
Con as Equa ion (1) wi h he i s o mula lis ed in he en y o sequence A147613
in OEIS which equi es loa ing poin a i hme ic due o he compu a ion o loge(2)
and he Lambe W unc ion.
2.2. In e lea ing Func ions
Typically, he compu a ion o C¬P equi es he in e sion o ¬P, which can be
di icul o do. Fo ins ance, i ¬P(n) is a polynomial in no deg ee 5 o mo e
hen by he Abel-Ru ini heo em i is in gene al no sol able in adicals. Howe e ,
i he sequence { ¬P(n)}is in e lea ed wi h ano he sequence {α(n)} ha is mo e
easily in e ible (ei he analy ically o compu a ionally), hen we can le e age his
o mo e e icien ly ind he complemen a y sequence P. Mo e p ecisely, assume
ha we a e gi en a eal- alued inc easing unc ion αsuch ha α(1) = 1 and
¬P(m−1) ≤α(m)≤ ¬P(m)
o all m. No e ha we do no equi e ha αis in ege - alued. We de ine he
inc easing and in ege - alued unc ion h(n) = max{m∈N+:α(m)≤n}. The idea
INTEGERS: 25 (2025) 7
is o choose αsuch ha his easie o compu e han in e ing ¬P. We can hen
compu e P(n) wi h one e alua ion o h(n).
Theo em 3. I ¬Pis such ha ¬P(m+ 1) − ¬P(m)≥m o all m, and α,h
a e as de ined abo e, hen
P(n) = 




n+h(n)+1 i n+h(n)≥ ¬P(h(n) + 1)
n+h(n)−1i n+h(n)≤ ¬P(h(n))
n+h(n)o he wise.
(2)
P oo . The condi ions on ¬Pimply ha we can apply Theo em 2. Nex no e ha
n+h(n)≥ ¬P(h(n) + 1) ≥ ¬P(h(n)) + h(n) implies ¬P(h(n)) ≤nand ha
n+h(n)≤ ¬P(h(n)) implies n< ¬P(h(n)) since h(n)≥1. The esul hen
ollows om he ac ha C¬P(n) = h(n) i ¬P(h(n)) ≤nand C¬P(n) = h(n)−1
o he wise.
This esul can be u he simpli ied depending on how close ¬Pand αa e.
Co olla y 1. Gi en he hypo hesis o Theo em 3, i ¬P(m)−α(m)< m, hen
P(n) = (n+h(n)+1 i n+h(n)≥ ¬P(h(n) + 1)
n+h(n)o he wise.
P oo . No e ha by de ini on o h,α(h(n)) ≤n. Ou o he h ee condi ions in
Equa ion (2), he second condi ion is ne e sa is ied by hypo hesis since o he wise
i eaches he con adic ion
n+h(n)−1< ¬P(h(n)) ≤h(n) + α(h(n)) −1≤n+h(n)−1.
Co olla y 2. Gi en he hypo hesis o Theo em 3, i ¬P(m)−α(m)≥m o m > 1,
hen
P(n) = (n+h(n)i n+h(n)> ¬P(h(n))
n+h(n)−1o he wise.
P oo . No e ha by de ini on o h,α(h(n) + 1) > n. Ou o he h ee condi ions in
Equa ion (2), he i s condi ion is ne e sa is ied by hypo hesis since o he wise i
eaches he con adic ion
n+h(n)≥ ¬P(h(n) + 1) ≥h(n) + α(h(n) + 1) > n +h(n).
INTEGERS: 25 (2025) 8
To illus a e, we will use hese esul s o ob ain o mulas o he non-k-gonal
numbe s, he non-k-gonal-py amidal numbe s, he non-k-simplex numbe s, he non-
sum-o -k- h-powe s and he non-cen e ed-k-gonal numbe s. Fu he mo e, we choose
hand αsuch ha hese o mulas can be implemen ed algo i hmically using in ege
a i hme ic.
2.2.1. Non-k-gonal Numbe s
The n- h k-gonal numbe s a e de ined as T(k, n) = (k−2)n(n−1)
2+n o k≥2 and
n≥1. Fo k= 2, he 2-gonal numbe s a e simply he na u al numbe s and hus
he e a e no non-2-gonal numbe s. In his sec ion we gi e a gene al o mula o he
n- h non-k-gonal numbe o k≥3.
Theo em 4. The n- h non-k-gonal numbe (k≥3) is gi en by
a(n) = 




n+jq2n
k−2k+ 1 i 2n > (k−2) jq2n
k−2kjq2n
k−2k+ 1
n+jq2n
k−2ko he wise,
(3)
i.e.,
a(n) = n+$ 2n
k−2%+ 2n > (k−2) $ 2n
k−2% $ 2n
k−2%+ 1!|.
Fo 3≤k≤10, his can be w i en as a(n) = n+jq2n
k−2+1
2k.
P oo . No e ha T(k, n + 1) −T(k, n)=(k−2)n+ 1 ≥n o k≥3. Fu he mo e,
T(k, n) is in e lea ed wi h α(n) = k−2
2(n−1)2wi h co esponding
h(n) = $ 2n
k−2%+ 1.
Since T(k, n)−α(n) = k
2(n−1) + 1 ≥n, we can apply Co olla y 2and ob ain
Equa ion (3).
Assume ha k≤10. The inequali y q2n
k−2−jq2n
k−2k≥1
2is equi alen o
2n≥(k−2) $ 2n
k−2% $ 2n
k−2%+ 1!+k−2
4.
Since 2nand (k−2) jq2n
k−2kjq2n
k−2k+ 1a e bo h e en and k−2
4≤2 his is
equi alen o 2n≥(k−2) jq2n
k−2kjq2n
k−2k+ 1+ 2 which in u n is equi alen
o 2n > (k−2) jq2n
k−2kjq2n
k−2k+ 1which is exac ly he condi ion in Equa ion
(3).
INTEGERS: 25 (2025) 9
Recall ha jq2n
k−2kcan be compu ed as  j2n
k−2k. Fo ins ance, in Py hon
3.x his can be implemen ed as isq (2*n//(k-2)). By se ing k= 3 o k= 4 in
Theo em 4, we ge he ollowing esul .
Co olla y 3. The n- h non- iangula numbe is gi en by n+⌊√2n+1
2⌋. The n- h
non-squa e numbe is gi en by n+⌊√n+1
2⌋.
In discussing [13, Example 4], i was shown ha he n- h non-squa e numbe is
n+⌊√n+1
2⌋, while discussing [13, Example 6] i was shown ha n+⌊pn+⌊√n⌋⌋
is a new o mula o he n- h non-squa e numbe . Theo em 1along wi h Co olla y 3
show he equi alence o hese wo o mulas. In [13, Example 5] i was epo ed ha
he n- h non- iangula numbe is n+⌊√2n+1
2⌋which also ollows om Co olla y
3.
Theo em 5. Fo k≥3, le be a eal numbe such ha −1≤ ≤k−4. Then
he n- h non-k-gonal numbe is gi en by
a(n) = 




n+jq2n+
k−2k+ 1 i 2n > (k−2) jq2n+
k−2kjq2n+
k−2k+ 1
n+jq2n+
k−2ko he wise.
(4)
By choosing =k+1
4−2, his can be simpli ied as a(n) = n+$ 2n−2+⌊k+1
4⌋
k−2+1
2%.
P oo . Le α(n) = k−2
2(n−1)2−
2wi h co esponding h(n) = jq2n+
k−2k+ 1. No e
ha since ≥ −1, T(k, n)−α(n) = k
2(n−1)+1+
2≥k
2(n−1) + 1
2≥n o n > 1.
Fu he mo e, α(n+ 1) −T(k, n) = (k−4)n
2−
2≥0 so we can apply Co olla y 2and
ob ain Equa ion (4).
Nex , q2n+
k−2−jq2n+
k−2k≥1
2is equi alen o
2n≥(k−2) $ 2n+
k−2% $ 2n+
k−2%+ 1!+k−2
4− .
By picking =k−10
4=k+1
4−2, his ensu es ha k−2
4− ≤2. Fu he mo e,
≥ −1 o k≥3. Since 2nand (k−2) jq2n+
k−2kjq2n+
k−2k+ 1a e bo h e en
his is equi alen o 2n≥(k−2) jq2n+
k−2kjq2n+
k−2k+ 1+ 2 which in u n is
equi alen o 2n > (k−2) jq2n+
k−2kjq2n+
k−2k+ 1, i.e., he condi ion in Equa ion
(4).
INTEGERS: 25 (2025) 16
Lemma 2. Fo each eal numbe bsuch ha ak−1
ak−1<b<ak−1
ak,
ak(n+b)k≤a(n)≤ak(n+1+b)k
o all su icien ly la ge n. I in addi ion k≥3, hen
ak(n+b)k+n≤a(n)≤ak(n+1+b)k
o all su icien ly la ge n.
P oo . Le ˜a(n) = Pk
i=0 aini, hen |a(n)−˜a(n)| ≤ 1. Nex no e ha
ak(n+b)k−˜a(n) = (akb−ak−1)nk−1+ 1(n)
whe e 1(n) is a polynomial o deg ee k−2 o less. Since akb−ak−1<0, i
ollows ha ak(n+b)k−˜a(n)<−1 and hus ak(n+b)k−a(n)<0 o su icien ly
la ge n. Simila ly, ak(n+b+ 1)k−˜a(n)=(ak(b+ 1) −ak−1)nk−1+ 2(n) o a
polynomial 2(n) o deg ee k−2 o less. Since ak(b+1)−ak−1>0, his means ha
ak(n+b+ 1)k−˜a(n)>1 and hus ak(n+b+ 1)k−a(n)>0 o la ge enough n.
Finally, i k≥3, he ac s ha ak(n+b)k+n−˜a(n)=(akb−ak−1)nk−1+n+ 1(n),
(akb−ak−1)<0, and n+ 1(n) is a polynomial o deg ee k−2 o less imply ha
ak(n+b)k+n−˜a(n)<−1 and hus ak(n+b)k+n−a(n)<0 o la ge enough
n.
No e ha a(n+ 1) −a(n)≥n o la ge enough nsince ak>0. By choosing
α(m) = ak(m+b)kwi h co esponding h(n) = jk
qn
ak−bk, o la ge enough n he
n- h e m o he complemen a y sequence o a(n) can be ound using one e alua ion
o he unc ion h. In pa icula , Theo em 3implies he ollowing esul .
Theo em 13. Le {c(n)}be he complemen a y sequence o he sequence {a(n)}.
I ak−1
ak−1<b<ak−1
akand h(n) = jk
qn
ak−bk, hen he e exis s n0>0such ha
o all n≥n0,
c(n) = 




n+h(n)+1 i n+h(n)≥a(h(n) + 1)
n+h(n)−1i n+h(n)≤a(h(n))
n+h(n)o he wise.
This can be implemen ed o he ollowing special case using he in ege k- h
oo unc ion n→ ⌊ k
√n⌋discussed in Sec ion 1by choosing b=jak−1
akk.

INTEGERS: 25 (2025) 17
Co olla y 6. Le {c(n)}be he complemen a y sequence o he sequence {a(n)}. I
ak−1
akis no an in ege , hen he e exis s n0>0such ha o all n≥n0,
c(n) =































n+jk
qn
akk−jak−1
akk+ 1 i n+jk
qn
akk−jak−1
akk≥
ajk
qn
akk−jak−1
akk+ 1
n+jk
qn
akk−jak−1
akk−1i n+jk
qn
akk−jak−1
akk≤
ajk
qn
akk−jak−1
akk
n+jk
qn
akk−jak−1
akko he wise.
Simila ly, Co olla y 2implies he ollowing esul .
Co olla y 7. Le k≥3and le {c(n)}be he complemen a y sequence o he
sequence {a(n)}. I ak−1
ak−1< b < ak−1
akand h(n) = jk
qn
ak−bk, hen he e exis s
n0>0such ha o all n≥n0,
c(n) = (n+h(n)i n+h(n)> a(h(n))
n+h(n)−1o he wise.
Co olla y 8. Le k≥3and le {c(n)}be he complemen a y sequence o he
sequence {a(n)}. I ak−1
akis no an in ege , hen he e exis s n0>0such ha o
all n≥n0,
c(n) = 












n+jk
qn
akk−jak−1
akki n+jk
qn
akk−jak−1
akk>
ajk
qn
akk−jak−1
akk
n+jk
qn
akk−jak−1
akk−1o he wise.
2.2.8. Compu ing Cha ac e is ic Func ions
I his easily compu able, hen his can lead o an e icien algo i hm o compu e he
cha ac e is ic unc ion χ¬Po ¬P. I is clea ha i ¬P(m) = n, hen h(n) = m.
This implies ha χ¬P(n) = 1 i and only i ¬P(h(n)) = n, i.e.,
χ¬P(n) = J ¬P(h(n)) = nK.
INTEGERS: 25 (2025) 18
As an example, conside he cha ac e is ic unc ion χ(n) o 4-simplex numbe s, i.e.,
numbe s o he o m m
4 o some m(OEIS A256436). Using h(n) = ⌊4
√24n⌋−1,
we see ha χ(n) = 1 i and only i n=⌊4
√24n⌋+2
4. This o mula is simple han
he i s o mula in he en y o OEIS A256436 gi en by
χ(n) = $p4√24n+ 1 + 5
2−3
2%−


q4p24(n−1) + 1 + 5
2−3
2


.
2.3. Bisec ion Sea ch
Theo em 1shows ha i ¬P(n) g ows quad a ically (o as e ), hen he numbe
o s eps needed o ind Pusing he unc ion i e a ion me hod is no mo e han
wo. Nume ical expe imen s sugges a simila ela ionship o o he g ow a es. In
pa icula , hese expe imen s allow us o conjec u e he ollowing esul .
Conjec u e 2. Fo k≥1, i ¬P(n) g ows as e han n1+ 1
k, hen he numbe o
s eps needed o he unc ion i e a ion me hod o de e mine P(n) is no mo e han
k+ 1.
Fo he complemen a y sequences whe e Theo em 1is applicable (and his include
he sequences discussed in he abo e sec ions), he numbe o s eps is bounded by a
cons an independen o n. Fo o he ypes o sequences, his may no be he case.
In hese cases, a di e en me hod o inding ixed poin s is needed ha is mo e
e icien han he unc ion i e a ion me hod.
The unc ion i e a ion me hod can ake a la ge numbe o s eps o con e ge when
he se o in ege s ha sa is y Pis spa se. In his case, i migh be mo e op imal
o use a bisec ion sea ch me hod o ind he ixed poin o gn. To his end, we i s
ind an in e al [kmin, kmax] ha bounds P(n). Since we know ha P(n)≥n,
we ini ially se kmin =n. I a be e lowe bound o P(n) is known, his can be
assigned o he ini ial kmin. Ini ially we can also se kmax =nunless we know a
be e lowe o uppe bound o an app oxima ion o b o P(n) in which case we
se kmax =b.
We nex double his ini ial alue kmax epea edly un il gn(kmax)≤kmax. Then
a bisec ion sea ch is applied un il he smalles ixed poin is ob ained. The pseudo
code o his algo i hm is shown in Algo i hm 2. The numbe o s eps needed o
con e ge is on he o de o log2( P(n)) and is in gene al mo e e icien han he
unc ion i e a ion me hod in Sec ion 2.1, especially when he numbe s sa is ying P
a e spa se. To illus a e his, we show in Figu e 2 he numbe o s eps needed o
hese wo me hods o ob ain P(n) when P(m) deno es he logical s a emen “mis
a p oduc o exac ly 6 dis inc p imes” (OEIS A067885). We see ha he numbe
o s eps o he bisec ion me hod is much smalle han o he unc ion i e a ion
me hod.
INTEGERS: 25 (2025) 19
Algo i hm 2 Bisec ion sea ch on gn(x) o compu e P(n).
Requi e: ∈N, gn(x)▷compu es he minimal ixed poin o gn.
kmin ←n,kmax ←n.
while gn(kmax)> kmax do
kmax ←2kmax
end while
kmin ←max(kmin, kmax/2)
while kmax −kmin >1do
kmid =⌊(kmax +kmin)/2⌋
i g(kmid)≤kmid hen
kmax ←kmid
else
kmin ←kmid
end i
end while
e u n kmax
100101102103104105106107108
n
102
103
104
numbe o s eps
P
(
m
) deno es "
m
is a p oduc o exac ly 6 dis inc p imes"
unc ion i e a ion me hod
bisec ion sea ch
Figu e 2: Numbe o s eps o ind P(n) when P(m) deno es he s a emen “mis
a p oduc o exac ly 6 dis inc p imes”.
INTEGERS: 25 (2025) 20
2.4. Hyb id Me hod
Since in se e al well known cases he numbe o s eps ha he unc ion i e a ion
me hod e mina es in is small, we can ake ad an age o his by se ing he ini ial
kmin and kmax o g( )
n(n) o some small , say = 2. He e ( )deno es he - h
i e a e o he unc ion . The o al numbe o s eps is hen plus he numbe o
s eps o he bisec ion me hod. This is illus a ed in Algo i hm 3.
Algo i hm 3 Hyb id me hod. Fi s i e a ions o he unc ion i e a ion me hod
is used o ini ialize he bisec ion sea ch.
Requi e: ∈N, gn(x)▷compu es he minimal ixed poin o gn.
kmin ←g( )
n(n), kmax ←g( )
n(n).
while gn(kmax)> kmax do
kmax ←2kmax
end while
kmin ←max(kmin, kmax/2)
while kmax −kmin >1do
kmid =⌊(kmax +kmin)/2⌋
i g(kmid)≤kmid hen
kmax ←kmid
else
kmin ←kmid
end i
end while
e u n kmax
3. The n- h Te m o he Union o Di e ence o Two Sequences
Conside he ollowing scena io whe e {a(i)}and {b(i)}a e disjoin sequences o in-
ege s wi h co esponding coun ing unc ions Caand Cb. Fo ins ance, he sequence
acould be he se o squa e- ee numbe s and b he pe ec powe s. The goal is o
ind he n- h elemen in he so ed lis when aand ba e so ed oge he . In his
speci ic example o aand b, he join sequence (deno ed as c) is OEIS A304449.
O he examples o such join sequences a e o ins ance, OEIS A000430,A006899,
A089237,A126684,A168363,A174090, and A384419. Because he sequences aand
ba e disjoin , in his scena io, he coun ing unc ion CP(n) o he join sequence c
is simply he sum o he coun ing unc ions o aand bgi en by Ca(n) + Cb(n) and
he abo e algo i hms can be used o ind he n- h elemen o c.
When he wo sequences a e no disjoin , CP(n) = Ca(n) + Cb(n)−Ca∩b(n) by
he inclusion-exclusion p inciple and in some cases he in e sec ion o he sequences
can easily be de e mined. Fo ins ance, le pbe p ime and conside he sequence
INTEGERS: 25 (2025) 21
o numbe s ksuch ha kkis a p- h powe (OEIS A176693,A376379). I he p ime
ac o iza ion o kis k=Qipei
i, hen kk=Qipkei
i. Thus, kkis a p-powe i and
only i kei≡0 (mod p). Since pis p ime, he esidue classes o m a ield, and his
condi ion co esponds o when kis a mul iple o po eiis a mul iple o p o all i,
i.e., kis a p- h powe . Thus, his sequence is he union o he mul iples o pand he
p- h powe s wi h co esponding coun ing unc ions ⌊n/p⌋and ⌊p
√n⌋. The coun ing
unc ion o hei in e sec ion is ⌊p
√n/p⌋and hus he coun ing unc ion o he union
is ⌊n/p⌋+⌊p
√n⌋−⌊p
√n/p⌋.
Simila ly he coun ing unc ion o he union o squa es and powe s o 2 (OEIS
A188915) is gi en by ⌊√n⌋+⌊log2(n)⌋−⌊log2(n)/2⌋=⌊√n⌋+⌈log2(n)/2⌉. Sim-
ila ly, he coun ing unc ion o he sequence esul ing om combining aand band
emo ing hei in e sec ion is CP(n) = Ca(n) + Cb(n)−2Ca∩b(n). Fo an example
see OEIS A377025.
A complemen a y app oach can be used o compu e he di e ence o wo se-
quences by no ing ha i bis a subsequence o a, hen Ca b(n) = Ca(n)−Cb(n).
Fo ins ance, conside OEIS A388304 which is equal o OEIS A303606 wi hou
he e ms o OEIS A177492. Simila ly OEIS A388427 is equal o OEIS A303554
wi hou he non-composi es.
In compu e science, he e is some imes he need o ind he n- h smalles elemen
o an (la ge) uno de ed lis o leng h lwi hou ha ing o so he en i e lis . Typi-
cally, his is pe o med using a pa ial so (see, e.g., he Quickselec algo i hm [8])
which has an O(l) a e age pe o mance. The abo e scena io can be conside ed a
special case o his p oblem whe e he sequence can be decomposed in o kdisjoin
subsequences, he coun ing unc ions o he subsequences a e e icien ly compu ed,
and he leng h o he lis o elemen s is a p io i unknown. Using he abo e algo i hm
leads o a unning ime depending on nunlike he pa ial so algo i hm which has
a unning ime depending on he leng h lo he en i e lis .
4. Sequences o Repea ed Te ms
Since P(n), which is he complemen a y sequence o he sequence ¬P(n), can be
iewed as he sequence o in ege s skipping he alues o ¬P(n), we can conside he
unc ion P(n)−nwhich lis s consecu i e in ege s, each one o which is epea ed.
Fo example, conside he sequence o non-squa e numbe s (OEIS A000037) gi en by
P(n) = (2,3,5,6,7,8,10,11, . . .). The sequence P(n)−nis (1,1,2,2,2,2,3,3, . . .),
i.e., each in ege mappea s 2m imes in he sequence (OEIS A000194). Since
P(n) = n+⌊√n+1
2⌋, his implies ha he sequence (1,1,2,2,2,2,3,3, . . .) can be
w i en as ⌊√n+1
2⌋. Simila ly, he sequence P(n) o he non- iangula numbe s
co esponds o a sequence P(n)−nwhe e each in ege mappea s m imes and
hus can be w i en explici ly as ⌊√2n+1
2⌋(OEIS A002024). This sequence has

INTEGERS: 25 (2025) 22
been s udied in [11].
Mo e gene ally, gi en a sequence o eal numbe s a1, a2, . . ., conside a sequence
b(n) o n≥1 whe e each numbe am≥1 appea s β(m) imes consecu i ely:
a1, a1,...a1
| {z }
β(1) imes
, a2, a2,...a2
| {z }
β(2) imes
, . . .
The goal is o de e mine b(n) gi en n. The case o β(m) = md o a ixed dwas
s udied in [17].
We will conside he special case whe e ai=ias he app oach o he gene al case
is he same. Then P(n) = b(n) + n−1 skips an in ege a e e e y addi ional β(i)
numbe s, meaning he i- h alue skipped is β(i) + 1 plus he las numbe skipped.
In o he wo ds ¬P(n) = Pn
i=1(β(i) + 1) = n+Pn
i=1 β(i). We can hen apply he
esul s and algo i hms in he p e ious sec ions o ind P(n) and hus also b(n).
Since ¬P(n)− ¬P(n−1) = β(n) + 1, i in addi ion β(m)≥m−2, hen we
can apply Theo ems 1and 2 o ind b(n). To illus a e his app oach, conside
he sequence b(n) whe e each in ege mappea s m2 imes (OEIS A074279). Then
¬P(n) = n+Pn
i=1 i2=n+n(n+ 1)(2n+ 1)/6 (OEIS A145066). Theo em 11 in
Sec ion 2.2.5 shows ha
P(n) = (n+⌊3
√3n⌋i 6n > ⌊3
√3n⌋⌊3
√3n⌋+ 12⌊3
√3n⌋+ 1
n+⌊3
√3n⌋−1 o he wise.
This implies ha
b(n) = P(n)−n+1 = (⌊3
√3n⌋+ 1 i 6n > ⌊3
√3n⌋⌊3
√3n⌋+ 12⌊3
√3n⌋+ 1
⌊3
√3n⌋o he wise.
This o mula is simple han he o mula o his sequence gi en in [21]. Mo e gen-
e ally, a sequence b(n) whe e each in ege m epea s mk−1 imes can be compu ed
using he o mula
b(n) = (⌊k
√kn⌋+ 1 i kn > Pk−1
j=0 k
jB+
j⌊k
√kn⌋k−j
⌊k
√kn⌋o he wise.
Again, hese o mulas equi e only one e alua ion o ⌊k
√kn⌋.
This app oach is used o ind no el o mulas o sequences o epea ed in ege s
such as OEIS A056556,A056557,A056558,A108581,A108582,A127321,A180447,
A194847,A194848,A235463, and A360010. Fo ins ance, he sequence b(n) whe e
each in ege mis epea ed m+3
3 imes (OEIS A127321) can be exp essed as
b(n) = 


⌊4
p24(n+ 2)⌋−2 i n < ⌊4
√24(n+2)⌋+2
4
⌊4
p24(n+ 2)⌋−1 o he wise.
INTEGERS: 25 (2025) 23
As men ioned abo e, he exis ence o a simple o mula o Pdoes no imply a
simple o mula o ¬P. Howe e , he exis ence o a simple o mula o CPimplies
he exis ence o a simple o mula C¬Pwhich leads o e icien algo i hms o bo h
Pand ¬P. In Sec ion 5, we look a o he examples o logical s a emen s P, mainly
ela ed o he p ime ac o iza ions o numbe s, o which he e a e ela i ely e icien
algo i hms o compu ing CP(n) (and hus also C¬P(n)).
5. Some O he Explici ly Compu able Coun ing Func ions CP(n)
The algo i hm o compu ing he complemen a y sequence ¬P(n) equi es he com-
pu a ion o he coun ing unc ion CP(n). No e ha CP(n) is he la ges in ege
msuch ha P(m)≤n. I P(n) is e icien ly compu ed, hen he ac ha Pis
s ic ly inc easing means ha CPcan be compu ed ia a bisec ion sea ch (simila
o Algo i hm 2 o gn). An example o such unc ions Pis he case whe e P(m)
deno es he s a emen “q(x) = m o some posi i e in ege x”, wi h qa s ic ly
inc easing polynomial wi h in ege coe icien s.
In o he cases, he unc ion P(n) is mo e easily enume a ed sequen ially in
which case a nai e app oach would be o enume a e P(n) in o de o compu e
CP(n) and hen sol e o he ixed poin o gn. Howe e , his app oach o ind he
complemen a y sequence ¬P(n) is less e icien han simply enume a ing P(n) and
assigning he gaps be ween successi e e ms o ¬P(n).
On he o he hand, o se e al numbe heo e ical s a emen s P, compu ing
CP(n) can be mo e e icien han enume a ing P(n). Fo ins ance, he e exis s
algo i hms o compu ing he p ime coun ing unc ion π(x) ha a e mo e e icien
han enume a ing all π(x) p ime numbe s less han o equal o x[2].
The o mulas o he coun ing unc ion o squa e- ee numbe s2gi en by
⌊√n⌋
X
i=1
µ(i)⌊n/i2⌋
and he coun ing unc ion o pe ec powe s3gi en by
1−⌊log2(x)⌋
X
i=2
µ(i)(⌊i
√x⌋−1)
equi e he compu a ion o he M¨obius unc ion µ(n) which can be done e icien ly
using a sie e [3]. The coun ing unc ions o semip imes and k-almos p imes can be
exp essed using π(x) and a e ound in [1,24]. The coun ing unc ion o squa e- ee
2See [20] o a mo e e icien o mula.
3See [18] o an al e na i e o mula.
INTEGERS: 25 (2025) 24
k-almos p imes (i.e., numbe s ha a e p oduc s o kdis inc p imes) has a simila
o m in e ms o π(x) (see o ins ance, OEIS A067885).
Ano he example whe e CP(n) is easily ob ained is when P(m) deno es he s a e-
men “mis a epdigi in base b” (OEIS A139819). In his case,
CP(n) = (b−1)⌊logb(n)⌋+(b−1)n
b⌊logb(n)⌋+1 −1.
6. Conclusions
We s udy algo i hms o ind he n- h in ege ha sa is ies a ce ain condi ion P ia
a ixed poin app oach. We show ha he unc ion i e a ion me hod o sol e his
p oblem is equi alen o he Lambek-Mose me hod. Fu he mo e, we show ha
he wo-s ep i e a ion o he Lambek-Mose algo i hm equi ing 2 e alua ions o he
coun ing unc ion can be educed o a single e alua ion o he coun ing unc ion.
We show ha he use o sui able simple in e lea ing unc ions can simpli y he
in e sion o P o ob ain CP. We also p esen a bisec ion algo i hm ha is mo e
e icien when he numbe s sa is ying Pa e spa se.
Fo a pa icula condi ion P, his app oach is use ul no only in inding he n- h
e m o he complemen a y sequences ¬Pbu also he n- h e m o he o iginal
sequence Pi sel when compu ing CP(n) is mo e e icien han enume a ing Pup
o n. Fo ins ance, we ha e used his app oach in a ious Py hon p og ams o ind
he n- h e m o OEIS sequences wi hou enume a ing all n e ms. These sequences
include pe ec powe s (OEIS A001597,A075090,A075109), p ime powe s (OEIS
A000961,A246655,A246547,A025475), powe ul numbe s (OEIS A001694), k- ull
numbe s (OEIS A036966,A036967,A069492,A069493), squa e- ee numbe s (OEIS
A005117), semip imes (OEIS A001358), squa e- ee semip imes (OEIS A006881),
k-almos p imes (OEIS A014612,A014613,A014614), squa e- ee k-almos p imes
(OEIS A007304,A046386,A046387,A067885,A281222), Achilles numbe s (OEIS
A052486), o de s o p ope semi ields and wis ed ields (OEIS A088247,A088248),
p-smoo h numbe s (OEIS A003586,A051037,A002473,A051038,A080197), num-
be s wi h a leas one digi b−1 in base b(OEIS A074940,A337239,A337250),
p imes s a ing wi h digi b(OEIS A045707-A045715), sums o 3 squa es (OEIS
A000378), numbe s wi h exac ly kdi iso s (OEIS A030513,A030515,A030626,
A030627,A030632,A030633,A137484,A137485,A137488), selec ed si ing se-
quences [23] (OEIS A003159,A007417,A382744,A382745,A382746), cha ac e -
is ic unc ions (OEIS A256436,A387646), and complemen a y sequences (OEIS
A004215,A024619,A052485,A029742,A007916,A002808,A013929,A100959,
A139819,A374812,A090946,A057854,A185543,A138836,A138890,A325112,
A059485,A279622,A145397,A302058,A376573,A183300,A387644,A388077).
Finally, in e es ed eade s can ob ain Py hon p og ams o he compu a ion o
INTEGERS: 25 (2025) 25
he OEIS sequences discussed in his pape by accessing he en ies o he co e-
sponding OEIS sequences o he co esponding p og ams in he Gi Hub eposi o y
oeis-sequences [25].
Re e ences
[1] D. C i¸san and R. E ban, On he coun ing unc ion o semip imes, In ege s 21 (2021), #A122.
[2] M. Del´eglise and J. Ri a , Compu ing π(x): he Meissel, Lehme , Laga ias, Mille , Odlyzko
me hod, Ma h. Comp. 65 (213) (1996), 235–245.
[3] M. Del´eglise and J. Ri a , Compu ing he summa ion o he M¨obius unc ion, Exp. Ma h. 5
(4) (1996), 291–295.
[4] B. Fa hi, An explici o mula gene a ing he non-Fibonacci numbe s, p ep in , a Xi :
1105.1127.
[5] H. W. Gould, Non-Fibonacci numbe s, Fibonacci Qua .,3(1965), 177–183.
[6] R. L. G aham, D. E. Knu h, and O. Pa ashnik, Conc e e Ma hema ics: A Founda ion o
Compu e Science, Addison-Wesley, 2nd ed., 1994.
[7] T. Hea h, A His o y o G eek Ma hema ics, ol. 2, Cla endon P ess, 1921.
[8] C. A. R. Hoa e, Algo i hm 65: ind, Commun. ACM 4(7) (1961), 321–322.
[9] R. Honsbe ge , Essay 12, in Ingenui y in Ma hema ics, The Ma hema ical Associa ion o
Ame ica, 1970, 93–110.
[10] K. E. I e son, A P og amming Language, Wiley, 1962.
[11] D. E. Knu h, The A o Compu e P og amming, Addison-Wesley, 1968.
[12] D. E. Knu h, Two no es on no a ion, Ame . Ma h. Mon hly 99 (5) (1992), 403–422.
[13] J. Lambek and L. Mose , In e se and complemen a y sequences o na u al numbe s, Ame .
Ma h. Mon hly 61 (7) (1954), 454–458.
[14] K. MacMillan and J. Sondow, P oo s o powe sum and binomial coe icien cong uences ia
Pascal’s iden i y, Ame . Ma h. Mon hly 118 (6) (2011), 549–551.
[15] C. Mo ici, Rema ks on complemen a y sequences, Fibonacci Qua . 48 (4) (2010), 343–347.
[16] R. D. Nelson, Sequences which omi powe s, Ma h. Gaz. 72 (461) (1988), 208–211.
[17] M. A. Nyblom, Some cu ious sequences in ol ing loo and ceiling unc ions, Ame . Ma h.
Mon hly,109 (6) (2002), 559–564.
[18] M. A. Nyblom, A coun ing unc ion o he sequence o pe ec powe s, Aus al. Ma h. Soc.
Gaz. 33 (2006), 338–343.
[19] The On-Line Encyclopedia o In ege Sequences, A ailable online a h ps://oeis.o g.
[20] J. Pawlewicz, Coun ing squa e- ee numbe s, p ep in , a Xi :1107.4890.
[21] B. Pu ie skiy, In ege sequences: I egula a ays and in a-block pe mu a ions, p ep in ,
a Xi :2310.18466.