Problem 366: statement's orientation disagrees with every example in its commentary; quoted 1e22 bound extendable to 1e24

[papanokechi]

Summary

Problem 366's statement asks about 2-full $n$
with $n+1$ 3-full, but every example in its commentary runs the other way round —
3-full followed by 2-full. The statement's orientation looks like a transcription
error. Separately, the search bound the page quotes can be extended by a factor of
100 fairly cheaply, because the bound is inherited from a search over a much
larger space than problem 366 needs.

Filing here rather than on the problem page because it is a page-content question
rather than mathematical discussion, following the precedent of #355.

Amended. The first version of this issue quoted only the second paragraph of
the commentary and drew a further inference from it that does not survive the
full text — see the comment below. The full commentary is quoted verbatim in §1
and the unsupported inference has been removed. The orientation observation,
which is the substance, is unchanged.

1. The statement's orientation disagrees with every example given

The statement, verbatim:

Are there any $2$-full $n$ such that $n+1$ is $3$-full? That is, if $p\mid n$
then $p^2\mid n$ and if $p\mid n+1$ then $p^3\mid n+1$.

The commentary, verbatim and in full:

Erdős originally asked Mahler whether there are infinitely many pairs of
consecutive powerful numbers, but Mahler immediately observed that the answer is
yes from the infinitely many solutions to the Pell equation $x^2=8y^2+1$.

Note that $8$ is 3-full and $9$ is $2$-full. Erdős and Graham asked if this is
the only pair of such consecutive integers. Stephan has observed that
$12167=23^3$ and $12168=2^33^213^2$ (a pair already known to Golomb [Go70]) is
another example, but (by OEIS A060355) there are no other examples for
$n<10^{22}$.

In [Er76d] Erdős asks the weaker question of whether there are any consecutive
pairs of $3$-full integers (which is also discussed in problem B16 of Guy's
collection [Gu04]).

Turturean notes in the comments that the ABC conjecture implies there are only
finitely many such $n$.

The commentary is internally coherent as a narrative. The mismatch is between it
and the statement. By explicit factorisation:

pair	factorisation	statement asks: $n$ 2-full and $n+1$ 3-full	commentary exhibits: $n$ 3-full and $n+1$ 2-full
$(8,9)$	$2^3$, $3^2$	$8$ 2-full ✓, $9$ 3-full ✗ → fails	✓ ✓ → holds
$(12167,12168)$	$23^3$, $2^3\cdot3^2\cdot13^2$	$12167$ 2-full ✓, $12168$ 3-full ✗ ($27\nmid12168$) → fails	✓ ✓ → holds

The commentary's sentence "Note that 8 is 3-full and 9 is 2-full" states the
orientation explicitly, and the second example follows it. So the whole commentary
discusses 3-full → 2-full while the statement asks 2-full → 3-full.

One consequence worth separating out: under the statement as written, no
example is known at all, at any size — a materially different state of affairs
from the one the commentary describes, where two examples are known and the
question is whether more exist.

I am not claiming to know which orientation was intended, and the computation in
§2 deliberately covers both.

2. The quoted search bound

The commentary's "by OEIS A060355 there are no other examples for $n<10^{22}$"
comes from A060355's b-file, whose header reads:

Donovan Johnson, Table of n, a(n) for n = 1..39 (terms < $10^{22}$)

A060355 lists $k$ such that $k$ and $k+1$ are both merely powerful.
Problem 366 additionally needs one member to be 3-full, which is a much
sparser condition, so 366 does not need anything like the full A060355 search:

	density	count $\le 10^{24}$
powerful (A060355's space)	$\sim\frac{\zeta(3/2)}{\zeta(3)}x^{1/2}=2.1733,x^{1/2}$	$\approx2.2\times10^{12}$
cubefull (what 366 needs)	$\sim C,x^{1/3}$, $C\approx4.65$	$460{,}160{,}083$ (exact)

Enumerating cubefull $m$ and testing $m\pm1$ for powerfulness therefore reaches
much further than $10^{22}$ on ordinary hardware. Doing so gives:

There is no $n&lt;10^{24}$ with $n$ 2-full and $n+1$ 3-full. The only
$n&lt;10^{24}$ with $n$ 3-full and $n+1$ 2-full are $n=8$ and $n=12167$.

This covers both readings in §1, so it holds however that is resolved.

To be clear about what is and isn't new here: below $10^{22}$ the second
sentence reproduces what the page already asserts, and serves only as validation
of the method. The new content is the extension of the range from $10^{22}$ to
$10^{24}$, and the fact that the direction the statement literally asks about has
no example anywhere in that range either. It does not extend A060355 — a
corollary is only that any A060355 term between $3.888\times10^{21}$ (the largest
b-file term) and $10^{24}$ has neither member cubefull.

3. How this was checked

The powerfulness test avoids factorisation entirely, which is what makes the
range reachable. With $B=\lceil X^{1/5}\rceil$, trial divide by primes $p\le B$
and reject as soon as some $p$ divides exactly once; let $r$ be the remaining
cofactor. Every prime factor of $r$ exceeds $B$, so if $r$ is powerful with $k$
distinct primes then $r\ge B^{2k}$ and $r\le X=B^5$, forcing $k\le2$. For $k=1$,
$r=p^e$ is a perfect power; for $k=2$, $r=p^aq^b$ with $a,b\ge2$ and $a+b\le5$,
and $(2,3)$ would give $r&gt;B^5\ge r$ — so only $(2,2)$, a square, survives. Hence
$r$ is powerful iff $r$ is a perfect power.

Validation:

• The test agrees with an independent trial-division reference on all
  $n\le200{,}000$ exhaustively, 400 random 22-digit integers, 200 constructed
  powerful $a^2b^3$ near $10^{22}$, 60 values $p^3$, and 143 values $(pq)^2$ —
  zero disagreements.
• Boundary: the largest value tested is $X+1$ and $B$ is built from $X+2$, so
  $B^5\ge X+2&gt;X+1$; checked at $10^{18},10^{22},10^{24},10^{26}$.
• The candidate count was reproduced by a second algorithm sharing no code path
  with the first. Every cubefull $n$ factors uniquely as $a^3b^4c^5$ with $b,c$
  squarefree and coprime, turning the count into a double sum:

$X$	exact cubefull count	scan tested
$10^{14}$	198,767	198,766
$10^{16}$	947,753	947,752
$10^{18}$	4,480,253	4,480,252
$10^{20}$	21,055,958	21,055,957
$10^{22}$	98,566,055	98,566,054
$10^{24}$	460,160,083	460,160,082

The uniform difference of 1 is $m=1$, which the scan skips deliberately: it gives
$n=0$ in the forward direction and $(1,2)$ in the reverse, and 2 is not powerful.

• Every scale from $10^{14}$ up reproduces both known pairs and finds nothing in
  the direction the statement asks.
• Cross-check against Johnson's b-file: the only A060355 terms below $10^{22}$
  with a cubefull member are 8 and 12167; the scan returns exactly those. (As
  noted in §2, this is the fact the page itself asserts, so it validates the
  method rather than adding anything.)

A self-contained runnable reproduction is in a comment below.

Suggested action

The statement and the commentary should agree on which of $n$, $n+1$ is the 3-full
one, and the $10^{22}$ figure can be updated to $10^{24}$. I have not opened a PR
because neither the statement nor the commentary is in data/problems.yaml — that
file carries only status / OEIS / tag metadata — so this needs an edit on
erdosproblems.com rather than here. I did not want to guess the orientation, since
the two readings give materially different answers to "is anything known at all".

---

Disclosure: this issue and the supporting computation were produced with AI
assistance (GitHub Copilot CLI), as required by CONTRIBUTING.md. Nothing here has
been or will be submitted to the OEIS, where AI-generated submissions are
forbidden. The correctness argument in §3 is short and self-contained
specifically so it can be checked without trusting the code, and every scale is
cross-checked against independently known values.

[papanokechi]

Runnable reproduction

A search bound nobody else can run is a claim rather than a result, so here is the
whole thing as one self-contained file — no arguments, no dependencies beyond the
standard library (it uses gmpy2 if present, and falls back to pure Python if
not). It contains the cubefull generator, the factoring-free powerfulness test,
both search directions, and an independent count of the candidate set by the
a^3 b^4 c^5 decomposition, so it self-checks as it goes.

Timings here, single core, on an idle laptop:

python p366_repro.py N	candidates	wall	result
6	306	instant	none asked; 8, 12167 reverse
8	1,644	instant	none asked; 8, 12167 reverse
10	8,347	instant	none asked; 8, 12167 reverse
12	41,135	~1 s	none asked; 8, 12167 reverse
14	198,766	5.7 s	none asked; 8, 12167 reverse
16	947,752	44.7 s	none asked; 8, 12167 reverse

Each run also prints the exact cubefull count from the second algorithm and the
difference from the number actually tested, which is 1 at every scale — the
deliberate m = 1 skip explained in the issue body. The counts 307 / 1,645 /
8,348 / 41,136 / 198,767 / 947,753 are independently checkable.

The 10^{24} figure in the issue is the same code with the loop distributed
over 8 cores and the inner test kept identical; nothing about the mathematics
changes with the parallelisation, and the sequential file above is the honest
statement of the method.

#!/usr/bin/env python3
"""
Self-contained reproduction for the problem 366 search.

Single file, no arguments needed, pure Python with an optional gmpy2 speedup.
Reproduces the whole pipeline: cubefull generator, factoring-free powerfulness
test, both search directions, and an independent count of the candidate set by a
second algorithm.

    python p366_repro.py            # runs to 1e12, ~seconds
    python p366_repro.py 14         # runs to 1e14
    python p366_repro.py 16         # runs to 1e16, a few minutes single-core

Expected output at every scale >= 1e4:
    asked direction (n 2-full, n+1 3-full) : none
    reverse         (n 3-full, n+1 2-full) : 8, 12167

WHY THE INNER TEST NEEDS NO FACTORISATION
-----------------------------------------
Fix X and set B = ceil(X^(1/5)). Trial divide n <= X by primes p <= B, rejecting
the moment some p divides n exactly once. Let r be the surviving cofactor. Every
prime factor of r exceeds B, so if r is powerful with k distinct primes then
r >= B^(2k) and r <= X = B^5, forcing k <= 2.
  k = 1: r = p^e is a perfect power.
  k = 2: r = p^a q^b with a,b >= 2 and r > B^(a+b), so a+b <= 5; (2,3) would give
         r > B^5 = X >= r, a contradiction; so only (2,2), a perfect square.
Hence r is powerful  <=>  r is a perfect power. No factorisation anywhere.

The loop breaks once p*p > n, which is safe: the residue is then 1 or a single
prime, and a prime is not a perfect power.
"""
import sys
from math import isqrt

try:
    from gmpy2 import is_power as _is_power, iroot as _iroot

    def is_perfect_power(n):
        return bool(_is_power(n))

    def icbrt(n):
        return int(_iroot(n, 3)[0])
except ImportError:                                    # pure-Python fallback
    def _iroot_k(n, k):
        if n < 2:
            return n
        x = int(round(n ** (1.0 / k)))
        while x > 1 and x ** k > n:
            x -= 1
        while (x + 1) ** k <= n:
            x += 1
        return x

    def is_perfect_power(n):
        if n < 4:
            return n == 1
        for k in range(2, n.bit_length() + 1):
            r = _iroot_k(n, k)
            if r < 2:
                break
            if r ** k == n:
                return True
        return False

    def icbrt(n):
        return _iroot_k(n, 3)


def primes_upto(n):
    if n < 2:
        return []
    sieve = bytearray([1]) * (n + 1)
    sieve[0:2] = b'\x00\x00'
    for i in range(2, isqrt(n) + 1):
        if sieve[i]:
            sieve[i * i::i] = bytearray(len(sieve[i * i::i]))
    return [i for i in range(2, n + 1) if sieve[i]]


def make_powerful_test(limit):
    """Return is_powerful() valid for every 1 <= n <= limit."""
    B = 1
    while (B + 1) ** 5 <= limit:
        B += 1
    B += 1                                    # ceil, so that B**5 >= limit
    assert B ** 5 >= limit, (B, limit)
    ps = primes_upto(B)

    def is_powerful(n):
        if n <= 1:
            return n == 1
        m = n
        for p in ps:
            if p * p > m:
                break
            if m % p == 0:
                m //= p
                if m % p:
                    return False              # p divides exactly once
                while m % p == 0:
                    m //= p
        return m == 1 or is_perfect_power(m)

    return is_powerful, B, len(ps)


def cubefull_upto(limit):
    """Yield every cubefull m with 1 <= m <= limit, via DFS over a^3*b^4*c^5."""
    ps = primes_upto(icbrt(limit) + 1)

    def rec(idx, val):
        yield val
        for i in range(idx, len(ps)):
            p = ps[i]
            q = p * p * p
            if val > limit // q:
                break
            v = val * q
            while True:
                yield from rec(i + 1, v)
                if v > limit // p:
                    break
                v *= p

    yield from rec(0, 1)


def count_cubefull(X):
    """Independent count: n cubefull <=> n = a^3 b^4 c^5, b,c squarefree coprime."""
    lim4 = 1
    while (lim4 + 1) ** 4 <= X:
        lim4 += 1
    small = primes_upto(lim4 + 1)

    def squarefree(n):
        for p in small:
            if p * p > n:
                break
            if n % (p * p) == 0:
                return False
        return True

    total = 0
    b = 1
    while b ** 4 <= X:
        if squarefree(b):
            c = 1
            while b ** 4 * c ** 5 <= X:
                if c == 1 or (squarefree(c) and _coprime(b, c)):
                    total += icbrt(X // (b ** 4 * c ** 5))
                c += 1
        b += 1
    return total


def _coprime(a, b):
    while b:
        a, b = b, a % b
    return a == 1


def main():
    e = int(sys.argv[1]) if len(sys.argv) > 1 else 12
    X = 10 ** e
    is_powerful, B, npr = make_powerful_test(X + 2)
    print('X = 1e%d   B = %d   primes used = %d' % (e, B, npr))

    asked, reverse, tested = [], [], 0
    for m in cubefull_upto(X):
        if m == 1:
            continue                     # n=0 forward; (1,2) reverse, 2 not powerful
        tested += 1
        if m >= 2 and is_powerful(m - 1):
            asked.append(m - 1)          # n = m-1 is 2-full, n+1 = m is 3-full
        if is_powerful(m + 1):
            reverse.append(m)            # n = m is 3-full, n+1 is 2-full
    asked.sort()
    reverse.sort()

    exact = count_cubefull(X)
    print('cubefull tested        : %d' % tested)
    print('cubefull exact (2nd alg): %d   (difference %d = the m=1 skip)'
          % (exact, exact - tested))
    print('asked direction (n 2-full, n+1 3-full) : %s'
          % (asked if asked else 'none'))
    print('reverse         (n 3-full, n+1 2-full) : %s'
          % (reverse if reverse else 'none'))
    ok = (not asked) and reverse == [x for x in (8, 12167) if x <= X]
    print('MATCHES EXPECTED' if ok else 'UNEXPECTED - investigate')


if __name__ == '__main__':
    main()

---

Disclosure: produced with AI assistance (GitHub Copilot CLI), per CONTRIBUTING.md.

[papanokechi]

Correction to this issue

I've amended the body above. Recording what changed and why, rather than
overwriting silently.

What was wrong. The first version quoted only the commentary's second
paragraph and then drew this inference from it:

Under the commentary's reading, the specific question posed ("is this the only
pair") is answered in the negative two sentences later on the same page, by
(12167, 12168) — which is itself a term of A060355, the sequence the entry
links to.

That is literally true and substantively misleading, and I've removed it. The
commentary is recounting history, not posing a live question that its own next
sentence defeats: Erdős and Graham asked whether $(8,9)$ was the only such pair,
Golomb already had the second example in 1970, and the page records both together
with the search result that there is no third below $10^{22}$. There is nothing
inconsistent in that, and presenting it as though there were was a mistake on my
part.

What else changed. The commentary has four paragraphs, not one. The original
excerpt omitted Mahler's Pell-equation observation, Erdős's weaker question in
[Er76d] about consecutive pairs of 3-full integers (Guy B16), and Turturean's
remark that the ABC conjecture implies only finitely many such $n$. All four are
now quoted verbatim so nobody has to trust my excerpting. I've also flagged
explicitly in §2 that below $10^{22}$ my reverse-direction results reproduce what
the page already asserts, and serve as validation of the method rather than as new
information — the new content is the extension to $10^{24}$ and the fact that the
direction the statement literally asks about has no example there either.

What stands. The orientation mismatch, which is the substance of the issue.
The statement asks for 2-full $n$ with $n+1$ 3-full; the commentary's own words are
"8 is 3-full and 9 is 2-full", and both exhibited pairs are 3-full followed by
2-full. Verified by explicit factorisation ($9=3^2$ is not 3-full;
$27\nmid 12168$). That is unaffected by anything above.

This was caught in peer review of my own write-up before a maintainer had
responded, which is the good case; it should have been caught by reading the whole
page before filing, which is the version I'd rather have delivered. Apologies for
the churn.

---

Disclosure: produced with AI assistance (GitHub Copilot CLI), per
CONTRIBUTING.md.

[teorth]

Thank you — this is a careful catch, and the orientation point is convincing: a statement that contradicts every example in its own commentary is exactly what our comments: "ambiguous statement" flag exists for.

Acted on: problem 366 is now flagged in the database — 0677cd6.

The remaining half — that the page's quoted 1e22 bound can be extended to 1e24 — is content on the problem 366 page itself, and this database has no field that records search bounds. As CONTRIBUTING.md puts it:

In general, discussion of Erdős problems should occur on the web site for that problem. The issue system here is mostly intended for matters relating to the database entries.

So the best home for the bound (and for the wording fix, where Thomas Bloom can act on it) is the forum thread: https://www.erdosproblems.com/forum/thread/366

Closing as a routing matter, not a judgement on the content — please reopen if you think there is a further data/problems.yaml change I have missed.