%% \documentclass[preprint,review,12pt]{elsarticle}
%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout.
\documentclass[final,3p,times]{elsarticle}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true,allcolors=blue}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{caption}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{booktabs}
\usepackage{array}
\usepackage{float}
\usepackage{algorithm}
\usepackage{algpseudocode}
\makeatletter
\providecommand{\theHALG@line}{}
\renewcommand{\theHALG@line}{\thealgorithm.\arabic{ALG@line}}
\makeatother

\theoremstyle{plain}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Corollary}[Theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Remark}[Theorem]{Remark}

\journal{Hexagon}

\begin{document}

\begin{frontmatter}

\title{Powers of a Prime in the Image of Summatory Valuation Functions}

\author{Frank Vega}

\address{Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA}

\ead{vega.frank@gmail.com}

\begin{abstract}
J.-L. Nicolas asked how often a power of $2$ belongs to the image of $c(n)=\sum_{k\le n}2^{v_2(k)}$, where $v_2$ is the $2$-adic valuation, and showed that both the number $A(x)$ of exponents $a\le x$ with $2^a$ in the image and the number $B(x)$ of the other exponents tend to infinity. We prove the identity $c(n)=n+\frac12\sum_{i}i\,2^{i}$, the sum running over the positions of the binary digits $1$ of $n$, so that $2^a$ lies in the image of $c$ if and only if $2^{a+3}$ is a sum of distinct terms of the superincreasing sequence $(j2^j)_{j\ge1}$. For every exponent there is at most one possible largest term $K$, given by $K+\lceil\log_2K\rceil=a+3$, and no such $K$ exists exactly when $a=2^r+r-2$. The remaining exponents are decided by an explicit recursion on pairs of integers bounded by $a+3$, in at most $a+1$ steps. We give the closed formula $c(2^{K-2}+2^{K-s-2})=2^{K+h-3}$ for $s=2^k$, $h\equiv k\pmod{2^{k+1}}$ and $K=(2^{h+s}+s)/(2^s+1)$, and infinite explicit families of exponents $a$ for which $2^a$ is not in the image, indexed by $s=3$ and $s=2^i$; the families given by Nicolas are the cases $s=1$ and $s=2$. As a consequence, $A(x)\ge(2+o(1))\log_2x$ and $B(x)\ge(\frac54+\frac12\sum_{i\ge1}\frac{1}{2^i-1}+o(1))\log_2x=(2.0533\ldots+o(1))\log_2x$. We prove that the states of the recursion form a forest, rooted at the states $(J,0)$ and at the failing states, in which every state $(J',w')$ has exactly $v_2(J'+1+w')$ children; that the sets $S_J$ of successful states are symmetric; that exactly half of them lie in the tree of the root $(1,0)$; that $N(2k+1)=N(2k)$; that $4\mid N(J)$ for $J\ge4$; and that $S_J$ satisfies a recursion from the smallest elements upwards, with period $J/2$ for even $J$. The symmetry gives further explicit families, among them $c(2^{2^r}-1)=2^{2^r+r-1}$, and the improved bounds $A(x)\ge(3.9655\ldots+o(1))\log_2x$ and $B(x)\ge(2.8178\ldots+o(1))\log_2x$. For every prime $p$, the function $c_p(n)=\sum_{k\le n}p^{v_p(k)}$ counts the factor $1-X$ in $(1-X)\cdots(1-X^n)$ over $\mathbb{F}_p$; we extend to it the reduction, the unique candidate, the recursions and the symmetry, give explicit families, and describe completely the exponents rejected at the first step, which occur only for odd $p$. We also report experiments in exact integer arithmetic: every statement is checked by three independent methods, the values of $A(x)$ reproduce the table of Nicolas, the sets $S_J$ are computed for $J\le131072$, and $A(x)/x$ lies between $0.5132$ and $0.8750$ for $x=1000,2000,\dots,131000$.
\end{abstract}

\begin{keyword}
Arithmetic functions \sep $2$-adic valuation \sep Binary expansion \sep Superincreasing sequences \sep Polynomials over $\mathbb{F}_2$ \sep Open questions of Nicolas
\MSC[2020] 11A63 \sep 11A25 \sep 11B83 \sep 11N37
\end{keyword}

\end{frontmatter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
\label{sec:intro}
For a positive integer $k$ let $v_2(k)$ denote the exponent of $2$ in $k$. In a joint paper with J.~Dixmier, J.-L.~Nicolas considered the function
\begin{equation}
\label{eq:cdef}
c(n)=\sum_{k=1}^{n}2^{v_2(k)},\qquad n\ge1,
\end{equation}
which is the exponent of $1+X$ in the factorization of $(1+X)(1+X^2)\cdots(1+X^n)$ into irreducible factors over $\mathbb{F}_2[X]$, and in his list of open questions~\cite{nicolas2005open} he asked how often a power of $2$ belongs to the image of $c$. The sequence $(c(n))_{n\ge1}=1,3,4,8,9,11,12,20,\dots$ of the partial sums of the highest power of $2$ dividing $k$ is the sequence M2344 of the encyclopedia of Sloane and Plouffe~\cite{sloaneplouffe1995}. It satisfies the recurrence $c(2n)=2c(n)+n$ and the formulas $c(2^r)=2^{r-1}(r+2)$ and $c(2^r-1)=r2^{r-1}$~\cite{nicolas2005open}, and the recurrence splits at half, a class of recurrences whose identities and periodic oscillations are studied by Hwang, Janson and Tsai~\cite{hwangjansontsai2024}. With
\begin{equation}
\label{eq:Adef}
\mathcal{A}=\{a\ge0:\ 2^a\in c(\mathbb{N})\},\qquad A(x)=\#\{a\in\mathcal{A}:\ a\le x\},\qquad B(x)=\#\{a\in\mathbb{Z}\cap[0,x]:\ a\notin\mathcal{A}\},
\end{equation}
Nicolas showed that $A(x)\to\infty$ and $B(x)\to\infty$, and asked whether the behaviour of $A(x)$ can be made precise; his table gives, for instance, the values $635$ for $x=1000$ and $5963$ for $x=10000$~\cite{nicolas2005open}, which are the numbers of exponents $1\le a\le x$ in $\mathcal{A}$, that is $A(x)-1$ in the notation~\eqref{eq:Adef}, since $c(1)=2^0$ (Section~\ref{sec:experiments}). He obtained these limits from three families: $2^a\notin c(\mathbb{N})$ when $a=2^r+r-2$; $a+(2^a-11)/3\in\mathcal{A}$ for odd $a$; and $a+(2^a-10)/3\notin\mathcal{A}$ for even $a$~\cite{nicolas2005open}.

The same list contains a question on a family of fractions, namely the size of the largest numerator $A(N)$ of $\prod_{n\le N}((n+1)/n)^{\varepsilon(n)}$ with $\varepsilon(n)\in\{-1,0,1\}$; for that question de la Bret\`eche, Pomerance and Tenenbaum proved $\log A(N)=\{\kappa+o(1)\}N\log N$ with an explicit constant $\kappa\approx0.107005$~\cite{bretechepomerancetenenbaum2005}. The present paper is concerned with the question on $c(n)$ only.

\paragraph{Contributions} We prove the following results.
\begin{itemize}
\item The identity $c(n)=n+\frac12\sum_{i\in\mathcal{B}(n)}i\,2^{i}$, where $\mathcal{B}(n)$ is the set of positions of the binary digits $1$ of $n$, equivalently $c(n)=n+\sum_{k\ge1}2^{k-1}\lfloor n/2^k\rfloor$, and the equivalence $a\in\mathcal{A}\iff 2^{a+3}=\sum_{j\in T}j\,2^{j}$ for a finite set $T$ of positive integers (Lemma~\ref{lem:cformula}, Theorem~\ref{thm:equiv}).
\item The numbers $j2^j$ form a superincreasing sequence. Consequently, for every $a\ge0$ there is at most one integer $K\ge2$ that can be the largest element of $T$, namely the solution of $K+\lceil\log_2K\rceil=a+3$, and such a $K$ fails to exist exactly for $a=2^r+r-2$, $r\ge1$ (Theorem~\ref{thm:leading}). This recovers the first family of Nicolas and shows that it is the only obstruction of this kind.
\item A recursion on pairs of integers bounded by $a+3$ that decides whether $a\in\mathcal{A}$ in at most $a+1$ steps, without handling integers of size $2^a$ (Theorem~\ref{thm:step}, Corollary~\ref{cor:algo}).
\item Infinite explicit families of members of $\mathcal{A}$, given by the closed formula $c(2^{K-2}+2^{K-s-2})=2^{K+h-3}$ for $s=2^k$, $k\ge0$, $h\equiv k\pmod{2^{k+1}}$ and $K=(2^{h+s}+s)/(2^s+1)$ (Theorem~\ref{thm:members}), and infinite explicit families of non-members, indexed by $s=3$ and by $s=2^i$, $i\ge1$ (Theorem~\ref{thm:nonmembers}). The second and third families of Nicolas are the cases $s=1$ of Theorem~\ref{thm:members} and $s=2$ of Theorem~\ref{thm:nonmembers}. These families are complete in the following sense: they are exactly the exponents that Algorithm~\ref{alg:membership} decides in at most one iteration (Theorem~\ref{thm:firststep}).
\item Explicit lower bounds for both counting functions (Theorem~\ref{thm:counting}):
\[
A(x)\ge(2+o(1))\log_2x,\qquad B(x)\ge\Bigl(\frac54+\frac{E}{2}+o(1)\Bigr)\log_2x,\qquad E=\sum_{i\ge1}\frac{1}{2^i-1}=1.6066951\ldots,
\]
so that $\frac54+\frac E2=2.0533475\ldots$.
\item The states of the recursion form a forest: the roots are the states $(J,0)$, one at each level, and the failing states, whose number up to level $L$ is given by an explicit formula; each state $(J',w')$ has exactly $v_2(J'+1+w')$ children; and the initial states are the states with $J+1+w$ a power of $2$ (Theorem~\ref{thm:forest}). The root of the tree of a successful state is determined by the least element of its representing set, and exactly half of the successful states of each level lie in the tree of the root $(1,0)$ (Proposition~\ref{prop:roots}). The sets $S_J$ satisfy the recursion $S_J=\{c/2:\ c\in S_{J-1}\text{ even}\}\cup\{(c+J)/2:\ c\in S_{J-1}\text{ odd}\}$ for odd $J$ and $S_J=\{c/2,\ c/2+J/2:\ c\in S_{J-1}\text{ even}\}$ for even $J$; in particular $S_J$ is periodic with period $J/2$ for even $J$ (Theorem~\ref{thm:bottomup}). The symmetry yields three further explicit families, among them $c(2^{2^r}-1)=2^{2^r+r-1}$ (Theorem~\ref{thm:symfamilies}), and the improved bounds $A(x)\ge(3.9655\ldots+o(1))\log_2x$ and $B(x)\ge(2.8178\ldots+o(1))\log_2x$ (Theorem~\ref{thm:counting2}). The sets $S_J$ of successful states, the states in the trees of the roots $(J,0)$: the number $N(J)=|S_J|$ counts the sets $T\subseteq\{1,\dots,J\}$ with $\sum_{j\in T}j2^j\equiv0\pmod{2^{J+1}}$, $S_J$ is symmetric under $w\mapsto J-1-w$, $N(2k+1)=N(2k)$, and $4\mid N(J)$ for $J\ge4$ (Section~\ref{sec:states}).
\item The analogue for every prime $p$ (Section~\ref{sec:primes}), with the complete description of the immediate failures, the bottom-up recursion and the symmetry $w\mapsto(p-1)K-w$ (Theorems~\ref{thm:immediate} and~\ref{thm:primebottomup}): $c_p(n)=\sum_{k\le n}p^{v_p(k)}$ is the exponent of $1-X$ in $(1-X)\cdots(1-X^n)$ over $\mathbb{F}_p[X]$; the reduction to digit sums of the numbers $p^i((p-1)i+p)$, the unique candidate, the exponents $(p^g-1)/(p-1)+g-1$ without candidate, the recursion, and explicit families, among them a family of non-members with no analogue for $p=2$ (Theorems~\ref{thm:primes}, \ref{thm:primestep} and~\ref{thm:primefamilies}).
\item Experiments (Section~\ref{sec:experiments}) with exact integer arithmetic: a verification of the statements above by three independent methods, among them a brute-force search over $n\le2^{24}$; the values of $A(x)$ and $B(x)$ for $x\le20000$, which agree with the table of Nicolas; the sets $S_J$ for $J\le65536$, from which $A(x)$ is obtained for $x\le65000$; and the proportion of exponents in $\mathcal{A}$ among the candidates $K\in(2^{h-1},2^h]$ for $h\le16$.
\end{itemize}

Section~\ref{sec:reformulation} proves the identity and the equivalence, Section~\ref{sec:leading} treats the largest element of $T$, Section~\ref{sec:recursion} gives the recursion, Sections~\ref{sec:members} and~\ref{sec:nonmembers} give the explicit families, Section~\ref{sec:counting} proves the counting bounds, Section~\ref{sec:states} studies the successful states, Section~\ref{sec:primes} treats an arbitrary prime, Section~\ref{sec:experiments} reports the experiments and Section~\ref{sec:conclusion} concludes.

\paragraph{Notation} $\mathbb{N}=\{1,2,3,\dots\}$. For $n\ge1$, $\mathcal{B}(n)\subset\{0,1,2,\dots\}$ is the set of positions of the digits $1$ in the binary expansion of $n$, so that $n=\sum_{i\in\mathcal{B}(n)}2^i$. For $J\ge0$ we put
\begin{equation}
\label{eq:EJ}
\mathcal{E}_J=\Bigl\{\sum_{j\in T}j\,2^{j}:\ T\subseteq\{1,\dots,J\}\Bigr\},\qquad \mathcal{E}=\bigcup_{J\ge0}\mathcal{E}_J,
\end{equation}
with $\mathcal{E}_0=\{0\}$ (empty sum).

\section{The function $c(n)$ and sums of $j2^j$}
\label{sec:reformulation}
\begin{Lemma}
\label{lem:cformula}
For every $r\ge0$, $c(2^r)=2^{r-1}(r+2)$, and for every $n\ge1$,
\begin{equation}
\label{eq:cformula}
c(n)=\sum_{i\in\mathcal{B}(n)}2^{i-1}(i+2)=n+\frac12\sum_{i\in\mathcal{B}(n)}i\,2^{i}.
\end{equation}
\end{Lemma}
\begin{proof}
For $r\ge0$, the number of $k\in[1,2^r-1]$ with $v_2(k)=v$ is $2^{r-1-v}$ for $0\le v\le r-1$, so $c(2^r-1)=\sum_{v=0}^{r-1}2^v2^{r-1-v}=r2^{r-1}$ and $c(2^r)=r2^{r-1}+2^r=2^{r-1}(r+2)$. If $m\ge0$ and $1\le s<2^m$, then $v_2(2^m+k)=v_2(k)$ for $1\le k\le s$, hence $c(2^m+s)=c(2^m)+c(s)$. Writing $n=2^{n_1}+\dots+2^{n_t}$ with $n_1>\dots>n_t$ and applying this relation $t-1$ times gives $c(n)=\sum_{l=1}^{t}c(2^{n_l})=\sum_{i\in\mathcal{B}(n)}2^{i-1}(i+2)$. Finally $2^{i-1}(i+2)=\frac12 i2^i+2^i$ and $\sum_{i\in\mathcal{B}(n)}2^i=n$.
\end{proof}

The first equality of~\eqref{eq:cformula} is formula (7.4) of~\cite{nicolas2005open}. The second form is equivalent to $c(n)=n+\sum_{k\ge1}2^{k-1}\lfloor n/2^k\rfloor$: since $\lfloor n/2^k\rfloor=\sum_{i\in\mathcal{B}(n),\,i\ge k}2^{i-k}$,
\[
\sum_{k\ge1}2^{k-1}\Bigl\lfloor\frac{n}{2^k}\Bigr\rfloor=\sum_{i\in\mathcal{B}(n)}\sum_{k=1}^{i}2^{k-1}2^{i-k}=\sum_{i\in\mathcal{B}(n)}i\,2^{i-1}.
\]
The binary form $\frac12\sum_{i\in\mathcal{B}(n)}i2^i$ is the one used below.

\begin{Theorem}
\label{thm:equiv}
Let $a\ge0$. Then $a\in\mathcal{A}$ if and only if $2^{a+3}\in\mathcal{E}$. More precisely, if $T$ is a finite set of positive integers with $\sum_{j\in T}j2^j=2^{a+3}$, then $1\notin T$, and $n=\sum_{j\in T}2^{j-2}$ satisfies $c(n)=2^a$; conversely, if $c(n)=2^a$, then $T=\mathcal{B}(n)+2$ satisfies $\sum_{j\in T}j2^j=2^{a+3}$.
\end{Theorem}
\begin{proof}
By~\eqref{eq:cformula}, $8c(n)=\sum_{i\in\mathcal{B}(n)}(i+2)2^{i+2}=\sum_{j\in\mathcal{B}(n)+2}j2^j$, which gives the converse part. For the direct part, every $j\ge2$ gives $j2^j\equiv0\pmod8$, while $1\cdot2^1=2$; since $2^{a+3}\equiv0\pmod 8$, $1\notin T$. As $2^{a+3}>0$, $T\neq\emptyset$, so $n=\sum_{j\in T}2^{j-2}$ is a positive integer with $\mathcal{B}(n)=T-2$, and $8c(n)=\sum_{j\in T}j2^j=2^{a+3}$.
\end{proof}

\section{The largest element of $T$}
\label{sec:leading}
\begin{Lemma}
\label{lem:sum}
For every $J\ge0$, $\sum_{j=1}^{J}j2^j=(J-1)2^{J+1}+2$. In particular $\max\mathcal{E}_J=(J-1)2^{J+1}+2<(J+1)2^{J+1}$.
\end{Lemma}
\begin{proof}
The identity holds for $J=0$, and if it holds for $J$, then $(J-1)2^{J+1}+2+(J+1)2^{J+1}=J2^{J+2}+2$. The inequality is $2<2^{J+2}$.
\end{proof}

\begin{Lemma}
\label{lem:greedy}
Let $J\ge1$ and $V\in\mathcal{E}_J$ with $V>0$, and let $T\subseteq\{1,\dots,J\}$ with $\sum_{i\in T}i2^i=V$. Then $\max T$ is the largest $j\in\{1,\dots,J\}$ with $j2^j\le V$, and $T$ is unique. Consequently, if $V>0$ and $j$ is the largest element of $\{1,\dots,J\}$ with $j2^j\le V$, then $V\in\mathcal{E}_J$ if and only if $V-j2^j\in\mathcal{E}_{j-1}$.
\end{Lemma}
\begin{proof}
Let $m=\max T$, so $m2^m\le V$. If some $j$ with $m<j\le J$ satisfied $j2^j\le V$, Lemma~\ref{lem:sum} would give $V\le\sum_{i=1}^{m}i2^i<(m+1)2^{m+1}\le j2^j\le V$, a contradiction. Hence $m$ is determined by $V$, and uniqueness of $T$ follows by induction on $|T|$ applied to $V-m2^m\in\mathcal{E}_{m-1}$. For the last statement, if $V\in\mathcal{E}_J$ the representing set has largest element $j$, so $V-j2^j\in\mathcal{E}_{j-1}$; conversely, adding $j$ to a set representing $V-j2^j$ in $\mathcal{E}_{j-1}$ represents $V$ in $\mathcal{E}_J$.
\end{proof}

For $K\ge2$ put
\begin{equation}
\label{eq:beta}
h(K)=\lceil\log_2K\rceil,\qquad \beta(K)=K+h(K).
\end{equation}

\begin{Theorem}
\label{thm:leading}
Let $b\ge3$.
\begin{enumerate}
\item If $2^b\in\mathcal{E}$ and $T$ is the set representing $2^b$, then $K=\max T$ satisfies $K\ge2$ and $\beta(K)=b$.
\item The map $\beta$ is strictly increasing on $\{2,3,\dots\}$, and $\{b\ge3\}\setminus\beta(\{2,3,\dots\})=\{2^r+r+1:\ r\ge1\}$.
\item If $b=\beta(K)$ and $h=h(K)$, then $0\le2^h-K\le K-2$, and $2^b\in\mathcal{E}$ if and only if $2^K(2^h-K)\in\mathcal{E}_{K-1}$.
\end{enumerate}
In particular, for $a\ge0$: if $a=2^r+r-2$ with $r\ge1$, then $a\notin\mathcal{A}$; otherwise there is exactly one $K\ge2$ with $\beta(K)=a+3$, and $a\in\mathcal{A}$ if and only if $2^K(2^{h(K)}-K)\in\mathcal{E}_{K-1}$.
\end{Theorem}
\begin{proof}
(1) By Lemma~\ref{lem:sum}, $K2^K\le2^b\le(K-1)2^{K+1}+2$. If $K=1$ this gives $2^b=2$, contradicting $b\ge3$; so $K\ge2$. Put $g=b-K$. Then $2^g\ge K\ge2$, so $g\ge1$, and $2^g\le2K-2+2^{1-K}<2K-1$, hence $2^g\le2K-2$. Thus $K\le2^g<2K$, that is $g=\lceil\log_2K\rceil$ and $b=\beta(K)$.

(2) $\beta(K+1)-\beta(K)=1+\lceil\log_2(K+1)\rceil-\lceil\log_2K\rceil$, and $\lceil\log_2(K+1)\rceil>\lceil\log_2K\rceil$ exactly when $K$ is a power of $2$, in which case the difference of the ceilings is $1$. Hence $\beta$ increases by $1$ at each step except from $K=2^r$ to $K=2^r+1$, where $\beta(2^r)=2^r+r$ and $\beta(2^r+1)=2^r+r+2$; since $\beta(2)=3$, the values $b\ge3$ not taken are exactly $2^r+r+1$, $r\ge1$.

(3) Since $2^{h-1}<K\le2^h$, we have $K\ge2^{h-1}+1$, so $2^h\le2K-2$, which gives $0\le2^h-K\le K-2$. If $2^b\in\mathcal{E}$, part (1) and part (2) show that the largest element of the representing set is $K$, and Lemma~\ref{lem:greedy} gives $2^b-K2^K=2^K(2^h-K)\in\mathcal{E}_{K-1}$. Conversely, if $2^K(2^h-K)\in\mathcal{E}_{K-1}$, adding $K$ to the representing set represents $2^b$.

The final statement follows from Theorem~\ref{thm:equiv} with $b=a+3$.
\end{proof}

The exponents $a=2^r+r-2$ are those of the first family of Nicolas~\cite{nicolas2005open}. Theorem~\ref{thm:leading} shows that every other $a$ has exactly one candidate leading term, and that the candidates $K$ for $a\le x$ are the integers $2\le K\le K_{\max}(x)$, where $K_{\max}(x)$ is the largest $K$ with $\beta(K)\le x+3$.

\section{A recursion on small integers}
\label{sec:recursion}
By Theorem~\ref{thm:leading}(3), the membership of $a$ in $\mathcal{A}$ is the question whether $2^{J+1}w\in\mathcal{E}_J$ for the pair $(J,w)=(K-1,2^h-K)$, which satisfies $J\ge1$ and $0\le w\le J-1$. We call such a pair a \emph{state}, and we call it \emph{successful} if $2^{J+1}w\in\mathcal{E}_J$.

\begin{Theorem}
\label{thm:step}
Let $(J,w)$ be a state, that is $J\ge1$ and $0\le w\le J-1$.
\begin{enumerate}
\item If $w=0$, the state is successful.
\item If $w\ge1$, then $J\ge2$; let $s$ be the least integer $\sigma\ge1$ with $2^\sigma w+\sigma\ge J+1$. Then $1\le s\le J-1$, and:
\begin{enumerate}
\item if $2^{s-1}w+s=J+1$, the state is not successful;
\item otherwise $w'=2^sw+s-J-1$ satisfies $0\le w'\le J-s-1$, the pair $(J-s,w')$ is a state, and $(J,w)$ is successful if and only if $(J-s,w')$ is successful.
\end{enumerate}
\end{enumerate}
\end{Theorem}
\begin{proof}
(1) $0\in\mathcal{E}_J$. (2) Since $1\le w\le J-1$, $J\ge2$. For $\sigma=J-1$ we have $2^{J-1}w+J-1\ge2+J-1=J+1$, so $s$ exists and $s\le J-1$. Put $V=2^{J+1}w>0$ and $j=J+1-s$, so $2\le j\le J$. For $\sigma\in\{1,\dots,J\}$ and $i=J+1-\sigma$, the inequality $i2^i\le V$ is equivalent to $J+1-\sigma\le2^\sigma w$; hence the largest $i\le J$ with $i2^i\le V$ corresponds to the least admissible $\sigma$, that is $i=j$. By Lemma~\ref{lem:greedy}, $V\in\mathcal{E}_J$ if and only if $V-j2^j=2^j(2^sw-j)=2^jw'\in\mathcal{E}_{j-1}$, where $w'=2^sw-j=2^sw+s-J-1\ge0$.

We bound $w'$ from above. If $s=1$, then $w'=2w-J\le J-2=j-2$. If $s\ge2$, the minimality of $s$ gives $2^{s-1}w+s-1\le J$, hence $2^sw\le2J+2-2s$ and $w'\le J+1-s=j$. Moreover $w'=j-1$ would mean $2^sw=2j-1$, which is impossible because $2^sw$ is even. Therefore either $w'\le j-2$ or $w'=j$, and $w'=j$ is equivalent to $2^sw=2j$, that is $2^{s-1}w+s=J+1$ (which cannot occur for $s=1$ since $w\le J-1$).

In case (a), $w'=j$ and $2^jw'=j2^j>(j-2)2^j+2=\max\mathcal{E}_{j-1}$ by Lemma~\ref{lem:sum}, since $2^{j+1}>2$; hence $V\notin\mathcal{E}_J$. In case (b), $w'\le j-2=(J-s)-1$ and $J-s=j-1\ge1$, so $(J-s,w')$ is a state, and $2^jw'=2^{(J-s)+1}w'$, so $V\in\mathcal{E}_J$ if and only if $(J-s,w')$ is successful.
\end{proof}

\begin{algorithm}[H]
\caption{Membership of $a$ in $\mathcal{A}$}
\label{alg:membership}
\begin{algorithmic}[1]
\Require an integer $a\ge0$
\State $b\gets a+3$
\If{there is no $K\ge2$ with $K+\lceil\log_2K\rceil=b$}
\State \Return $a\notin\mathcal{A}$
\EndIf
\State $h\gets\lceil\log_2K\rceil$; $J\gets K-1$; $w\gets2^h-K$
\While{$w\ge1$}
\State $s\gets$ least $\sigma\ge1$ with $2^\sigma w+\sigma\ge J+1$
\If{$2^{s-1}w+s=J+1$}
\State \Return $a\notin\mathcal{A}$
\EndIf
\State $w\gets2^sw+s-J-1$; $J\gets J-s$
\EndWhile
\State \Return $a\in\mathcal{A}$
\end{algorithmic}
\end{algorithm}

\begin{Corollary}
\label{cor:algo}
Algorithm~\ref{alg:membership} decides whether $a\in\mathcal{A}$. It performs at most $K-2\le a+1$ iterations of the loop, and every integer it handles, other than the bound $2^h\le2K-2$ of the initial step, is at most $2K\le2a+6$. When it returns $a\in\mathcal{A}$, the indices $j=J+1-s$ produced at the successive iterations, together with $K$, form the set $T$ of Theorem~\ref{thm:equiv}, and $n=\sum_{j\in T}2^{j-2}$ satisfies $c(n)=2^a$.
\end{Corollary}
\begin{proof}
Correctness follows from Theorems~\ref{thm:leading} and~\ref{thm:step}. Each iteration decreases $J$ by $s\ge1$ and keeps $J\ge1$, starting from $J=K-1$, so there are at most $K-2$ iterations; $K\le\beta(K)-1=a+2$. Throughout, $0\le w\le J-1\le K-2$, and in the computation of $s$ only $\sigma\le s$ are tested, with $2^{\sigma}w+\sigma\le2^sw+s\le2J+2-s\le2K$ for $s\ge2$ by the proof of Theorem~\ref{thm:step}, and $2w+1\le2K$ for $s=1$. The last statement follows from the proof of Theorem~\ref{thm:step} and Lemma~\ref{lem:greedy}.
\end{proof}

\begin{Example}
For $a=5$, $b=8=\beta(5)$, $h=3$ and the initial state is $(4,3)$. The loop gives $s=1$ and $(3,2)$, then $s=1$ and $(2,1)$, then $s=1$ and $(1,0)$, so $5\in\mathcal{A}$ with $T=\{5,4,3,2\}$ and $n=2^3+2^2+2+1=15$; indeed $c(15)=32$~\cite{nicolas2005open}. For $a=6$, $b=9=\beta(6)$, $h=3$ and the initial state is $(5,2)$; here $s=2$ and $2^{1}\cdot2+2=6=J+1$, so $6\notin\mathcal{A}$.
\end{Example}

\section{Explicit members of $\mathcal{A}$}
\label{sec:members}
\begin{Theorem}
\label{thm:members}
\begin{enumerate}
\item For every $r\ge1$, $c\bigl(2^{2^r-2}\bigr)=2^{2^r+r-3}$; thus $2^r+r-3\in\mathcal{A}$.
\item Let $k\ge0$, $s=2^k$, and let $h\ge k+2$ with $h\equiv k\pmod{2^{k+1}}$. Then
\begin{equation}
\label{eq:Kmember}
K=\frac{2^{h+s}+s}{2^s+1}
\end{equation}
is an integer with $2^{h-1}<K<2^h$ and $K-s\ge2$, and
\begin{equation}
\label{eq:member}
c\bigl(2^{K-2}+2^{K-s-2}\bigr)=2^{K+h-3};
\end{equation}
thus $K+h-3=\beta(K)-3\in\mathcal{A}$.
\end{enumerate}
\end{Theorem}
\begin{proof}
(1) By Lemma~\ref{lem:cformula} with $m=2^r-2$, $c(2^m)=2^{m-1}(m+2)=2^{2^r-3}2^r$.

(2) Modulo $2^s+1$ we have $2^s\equiv-1$, hence $2^{2s}\equiv1$. Writing $h=k+2sq$ with $q\ge0$ we get $2^h\equiv2^k=s$, and therefore $2^{h+s}+s\equiv-2^h+s\equiv0\pmod{2^s+1}$, so $K$ is an integer. Next, $K=2^h-(2^h-s)/(2^s+1)$. Since $s=2^k<2^h$, $K<2^h$; since $2^s+1\ge3$, $(2^h-s)/(2^s+1)<2^{h-1}$, so $K>2^{h-1}$. As $h\ge k+2$, $s\le2^{h-2}$ and $K-s\ge2^{h-1}+1-2^{h-2}\ge2$. By Lemma~\ref{lem:cformula}, with $K-2>K-s-2\ge0$,
\[
c\bigl(2^{K-2}+2^{K-s-2}\bigr)=2^{K-3}K+2^{K-s-3}(K-s)=2^{K-s-3}\bigl(K(2^s+1)-s\bigr)=2^{K-s-3}2^{h+s}=2^{K+h-3}.
\]
Since $2^{h-1}<K<2^h$, $h=h(K)$ and $K+h=\beta(K)$.
\end{proof}

For $k=0$ ($s=1$) the condition is that $h\ge2$ is even, $K=(2^{h+1}+1)/3$, and the exponent is $K+h-3=(h+1)+(2^{h+1}-11)/3$; with $a=h+1$ this is the family $a+(2^a-11)/3$, $a$ odd, of Nicolas~\cite{nicolas2005open}. For $k=1$ ($s=2$), $h\equiv1\pmod4$; for instance $h=5$ gives $K=26$ and $c(2^{24}+2^{22})=2^{28}$.

\section{Explicit non-members of $\mathcal{A}$}
\label{sec:nonmembers}
\begin{Theorem}
\label{thm:nonmembers}
Let $s\ge2$ and $h\ge1$ with $s<2^h$ and $2^h\equiv s\pmod{2^{s-1}+1}$. Then
\begin{equation}
\label{eq:Knon}
K=\frac{2^{h+s-1}+s}{2^{s-1}+1}
\end{equation}
is an integer with $2^{h-1}<K<2^h$, and $K+h-3=\beta(K)-3\notin\mathcal{A}$. The hypotheses hold in the following cases:
\begin{enumerate}
\item $s=2^i$ with $i\ge1$, and $h>i$ with $h\equiv i\pmod{2(2^i-1)}$;
\item $s=3$, and $h\equiv3\pmod4$.
\end{enumerate}
\end{Theorem}
\begin{proof}
Put $M=2^{s-1}+1$. Since $2^{s-1}\equiv-1\pmod M$, $2^{h+s-1}+s\equiv-2^h+s\equiv0\pmod M$, so $K$ is an integer. As $K=2^h-(2^h-s)/M$ with $0<2^h-s$ and $M\ge3$, we get $2^{h-1}<K<2^h$, hence $h=h(K)$ and $K+h=\beta(K)$. By Theorem~\ref{thm:equiv} and Theorem~\ref{thm:leading}, $K+h-3\in\mathcal{A}$ if and only if the state $(J,w)=(K-1,2^h-K)$ is successful. Here $w\ge1$, and $K\ge3$ because $s\ge2$ and $s<2^h$ force $h\ge2$; so $J\ge2$. The definition of $K$ is equivalent to $K(2^{s-1}+1)=2^{h+s-1}+s$, that is
\[
2^{s-1}w+s=K=J+1.
\]
We check that $s$ is the least $\sigma\ge1$ with $2^\sigma w+\sigma\ge J+1$. The function $\sigma\mapsto2^\sigma w+\sigma$ is increasing; at $\sigma=s-1\ge1$ its value is $J$, and at $\sigma=s$ it is $2(K-s)+s=2K-s$, which is at least $K$ because $K-s=(2^h-s)(1-1/M)>0$. Hence Theorem~\ref{thm:step}(2a) applies, and the state is not successful.

Case (1): $M=2^{s-1}+1$ with $s=2^i$, so $2^{2(s-1)}\equiv1\pmod M$ and $h=i+2(s-1)q$ gives $2^h\equiv2^i=s$; and $s=2^i<2^h$ because $h>i$. Case (2): $M=5$, $2^4\equiv1$ and $2^3\equiv3\pmod5$, so $h\equiv3\pmod4$ gives $2^h\equiv3=s$; and $3<2^h$ because $h\ge3$.
\end{proof}

For $s=2$ the condition is that $h\ge3$ is odd, $K=(2^{h+1}+2)/3$, and the exponent is $K+h-3=(h+1)+(2^{h+1}-10)/3$; with $a=h+1$ this is the family $a+(2^a-10)/3$, $a$ even, of Nicolas~\cite{nicolas2005open}. For $s=3$ and $h=3$, $K=7$ and $7\notin\mathcal{A}$; for $s=4$ and $h=8$, $K=228$ and $233\notin\mathcal{A}$.

The families of Theorems~\ref{thm:members} and~\ref{thm:nonmembers} are exactly the exponents decided by at most one iteration of Algorithm~\ref{alg:membership}.

\begin{Theorem}
\label{thm:firststep}
Let $a\ge0$ have a candidate $K$ (Theorem~\ref{thm:leading}), let $h=h(K)$, and let $(J,w)=(K-1,2^h-K)$ be the initial state.
\begin{enumerate}
\item Algorithm~\ref{alg:membership} returns $a\in\mathcal{A}$ without any iteration if and only if $K=2^h$, that is, $a$ is an exponent of Theorem~\ref{thm:members}(1).
\item Algorithm~\ref{alg:membership} returns $a\in\mathcal{A}$ after exactly one iteration if and only if $a$ is an exponent of Theorem~\ref{thm:members}(2), that is, $K=(2^{h+s}+s)/(2^s+1)$ with $s=2^k$, $k\ge0$, $h\ge k+2$ and $h\equiv k\pmod{2^{k+1}}$.
\item Algorithm~\ref{alg:membership} returns $a\notin\mathcal{A}$ at its first iteration if and only if $a$ is an exponent of Theorem~\ref{thm:nonmembers}(1) or~(2), that is, $K=(2^{h+s-1}+s)/(2^{s-1}+1)$ with either $s=2^i$, $i\ge1$, $h>i$ and $h\equiv i\pmod{2(2^i-1)}$, or $s=3$ and $h\equiv3\pmod4$.
\end{enumerate}
\end{Theorem}
\begin{proof}
(1) The loop is not entered if and only if $w=0$, that is $K=2^h$.

We use the following fact on residues. Let $m\ge1$ and $N=2^m+1$. Since $2^m\equiv-1\pmod N$, the residues of the powers $2^e$, $e\ge0$, are $2^l$ and $N-2^l$ for $0\le l\le m-1$; these $2m$ residues are distinct, because $N-2^l\ge2^{m-1}+1>2^{m-1}\ge2^{l'}$, so $2$ has order $2m$ modulo $N$ and $2^e\equiv2^l\pmod N$ with $0\le l\le m-1$ holds if and only if $e\equiv l\pmod{2m}$.

(2) Suppose $w\ge1$. The first iteration ends with $w'=0$, without failure, if and only if $2^sw+s=J+1=K$ for the least admissible $s$. Conversely, if $2^\sigma w+\sigma=K$ for some $\sigma\ge1$, then $\sigma$ is the least admissible value, because $2^{\sigma-1}w+\sigma-1=(K+\sigma-2)/2<K$ (as $\sigma<K$), and the failure condition $2^{\sigma-1}w+\sigma=(K+\sigma)/2=K$ would give $K=\sigma$, which is impossible since $K=2^\sigma w+\sigma>\sigma$. Hence one-iteration success is equivalent to the existence of $s\ge1$ with $2^s(2^h-K)+s=K$, that is $K(2^s+1)=2^{h+s}+s$, which requires $2^{h+s}+s\equiv0$, that is $2^h\equiv s\pmod{2^s+1}$. Apply the fact with $m=s$: $s<2^s+1$, and $s=2^s+1-2^l$ with $l\le s-1$ would give $s\ge2^{s-1}+1>s$; hence $s=2^l$ for some $l$, which we call $k$, with $k\le s-1$, and $2^h\equiv2^k$ gives $h\equiv k\pmod{2^{k+1}}$. Moreover $w\ge1$ means $K<2^h$, which is $s<2^h$, that is $h>k$; with $h\equiv k\pmod{2^{k+1}}$ this gives $h\ge k+2^{k+1}\ge k+2$. Conversely, under these conditions Theorem~\ref{thm:members}(2) gives $K(2^s+1)=2^{h+s}+s$ with $1\le w$.

(3) Suppose $w\ge1$. By Theorem~\ref{thm:step}, the first iteration fails if and only if $2^{s-1}w+s=J+1=K$ for the least admissible $s$, and then $s\ge2$. Conversely, if $2^{\sigma-1}w+\sigma=K$ for some $\sigma\ge2$, the proof of Theorem~\ref{thm:nonmembers} shows that $\sigma$ is the least admissible value. Hence first-iteration failure is equivalent to the existence of $s\ge2$ with $K(2^{s-1}+1)=2^{h+s-1}+s$, which requires $2^h\equiv s\pmod M$, $M=2^{s-1}+1$, and $w\ge1$ is $s<2^h$. Apply the fact with $m=s-1$; note $2\le s<M$. If $s=2^l$ with $l\le s-2$, then $l\ge2$, and $h\equiv l\pmod{2(s-1)}$, which with $s<2^h$ is case (1) of Theorem~\ref{thm:nonmembers} with $i=l\ge2$. Otherwise $s=M-2^l$ with $0\le l\le s-2$, that is $2^{s-1}+1-s=2^l$. For $s\ge4$ this is impossible, since $2^{s-2}<2^{s-1}+1-s<2^{s-1}$. For $s=2$, $l=0$ and $2^h\equiv M-1=2\pmod3$, that is $h$ odd, and $s<2^h$ gives $h\ge3$: case (1) with $i=1$. For $s=3$, $l=1$ and $2^h\equiv3\pmod5$, that is $h\equiv3\pmod4$: case (2). Conversely, Theorem~\ref{thm:nonmembers} shows that its exponents fail at the first iteration.
\end{proof}

Consequently, every exponent $a$ that is not of the form $2^r+r-2$ and is not covered by Theorems~\ref{thm:members} and~\ref{thm:nonmembers} requires at least two iterations of Algorithm~\ref{alg:membership}.

\section{Counting functions}
\label{sec:counting}
\begin{Theorem}
\label{thm:counting}
As $x\to\infty$,
\[
A(x)\ge2\log_2x-O(\log\log x),\qquad B(x)\ge\Bigl(\frac54+\frac E2\Bigr)\log_2x-O(\log\log x),
\]
where $E=\sum_{i\ge1}1/(2^i-1)=1.6066951\ldots$, so that $\frac54+\frac E2=2.0533475\ldots$.
\end{Theorem}
\begin{proof}
Let $x\ge16$ and $H=\lfloor\log_2x\rfloor-1\ge3$. If $1\le h\le H$ and $2\le K\le2^h$, then $\beta(K)-3\le2^h+h-3\le x/2+\log_2x\le x$. All exponents produced by Theorems~\ref{thm:members}(2) and~\ref{thm:nonmembers} are of the form $\beta(K)-3$ with $2^{h-1}<K<2^h$, and $\beta$ is injective (Theorem~\ref{thm:leading}(2)), so distinct values of $K$ give distinct exponents. For fixed $h$, the integer $K$ in~\eqref{eq:Kmember} and in~\eqref{eq:Knon} equals $2^h-(2^h-s)/(2^s+1)$ and $2^h-(2^h-s)/(2^{s-1}+1)$ respectively, both strictly increasing in $s$, so distinct values of $s$ in the same theorem give distinct values of $K$; a member and a non-member are distinct.

Members. Theorem~\ref{thm:members}(1) gives the $H$ exponents $\beta(2^h)-3$, $1\le h\le H$, which are distinct from those of part (2) since there $K<2^h$. For $0\le k\le\kappa=\lfloor\log_2H\rfloor$, the integers $h=k+2^{k+1}t$ with $1\le t\le\lfloor(H-k)/2^{k+1}\rfloor$ satisfy the hypotheses of Theorem~\ref{thm:members}(2) and $h\le H$; their number is at least $(H-k)/2^{k+1}-1$. Summing over $k$ and using $\sum_{k\ge0}k/2^{k+1}=1$ and $2^{-\kappa-1}H<1$,
\[
\sum_{k=0}^{\kappa}\Bigl(\frac{H-k}{2^{k+1}}-1\Bigr)\ge H\bigl(1-2^{-\kappa-1}\bigr)-1-(\kappa+1)\ge H-\log_2H-3.
\]
Hence $A(x)\ge2H-\log_2H-3=2\log_2x-O(\log\log x)$.

Non-members. Theorem~\ref{thm:leading} gives the $H$ exponents $2^r+r-2\le x$, $1\le r\le H$, which are not of the form $\beta(K)-3$. For $1\le i\le\kappa$, the integers $h=i+2(2^i-1)t$ with $1\le t\le\lfloor(H-i)/(2(2^i-1))\rfloor$ satisfy Theorem~\ref{thm:nonmembers}(1) and $h\le H$; their number is at least $(H-i)/(2(2^i-1))-1$. Since $\sum_{i>\kappa}1/(2(2^i-1))\le\sum_{i>\kappa}2^{-i}=2^{-\kappa}<2/H$ and $\sum_{i\ge1}i/(2(2^i-1))<\infty$, the sum over $i$ is at least $\frac E2H-O(\log H)$. Theorem~\ref{thm:nonmembers}(2) gives the integers $3\le h\le H$ with $h\equiv3\pmod4$, at least $H/4-1$ of them. Hence $B(x)\ge(1+\frac14+\frac E2)H-O(\log H)$, and $H=\log_2x+O(1)$.
\end{proof}

\section{Successful states}
\label{sec:states}
For $J\ge1$ let
\[
S_J=\{w:\ 0\le w\le J-1,\ 2^{J+1}w\in\mathcal{E}_J\},\qquad N(J)=|S_J|,
\]
so that $S_J$ is the set of $w$ for which the state $(J,w)$ of Section~\ref{sec:recursion} is successful. By Theorems~\ref{thm:equiv} and~\ref{thm:leading}, an exponent $a$ with candidate $K$ and $h=h(K)$ belongs to $\mathcal{A}$ if and only if $2^h-K\in S_{K-1}$.

\begin{Proposition}
\label{prop:Ncount}
\begin{enumerate}
\item For $J\ge1$, $N(J)=\#\{T\subseteq\{1,\dots,J\}:\ \sum_{j\in T}j2^j\equiv0\pmod{2^{J+1}}\}$.
\item For $h\ge1$, the number of $a\in\mathcal{A}$ whose candidate $K$ lies in $(2^{h-1},2^h]$ equals $\#\{K\in(2^{h-1},2^h]:\ 2^h-K\in S_{K-1}\}$.
\end{enumerate}
\end{Proposition}
\begin{proof}
(1) By Lemma~\ref{lem:greedy}, the map $T\mapsto\sum_{j\in T}j2^j$ is injective on the subsets of $\{1,\dots,J\}$. If $\sum_{j\in T}j2^j\equiv0\pmod{2^{J+1}}$, the sum equals $2^{J+1}w$ with $w\ge0$, and $2^{J+1}w\le(J-1)2^{J+1}+2$ by Lemma~\ref{lem:sum}, so $w\le J-1$ and $w\in S_J$; conversely every $w\in S_J$ is obtained from exactly one $T$. (2) The map $K\mapsto\beta(K)-3$ is injective (Theorem~\ref{thm:leading}), and $\beta(K)-3\in\mathcal{A}$ if and only if $2^{h}-K\in S_{K-1}$.
\end{proof}

\begin{Proposition}
\label{prop:symmetry}
For every $J\ge1$, $w\in S_J$ if and only if $J-1-w\in S_J$.
\end{Proposition}
\begin{proof}
For $J=1$, $S_1=\{0\}$. Let $J\ge2$, $w\in S_J$, and let $T\subseteq\{1,\dots,J\}$ represent $V=2^{J+1}w$. Since $J+1\ge3$, $V\equiv0\pmod8$, and as in the proof of Theorem~\ref{thm:equiv}, $1\notin T$. By Lemma~\ref{lem:sum}, $\sum_{j=2}^{J}j2^j=(J-1)2^{J+1}$, so the set $\{2,\dots,J\}\setminus T$ represents $(J-1)2^{J+1}-2^{J+1}w=2^{J+1}(J-1-w)$, and $J-1-w\in S_J$. Applying this to $J-1-w$ gives the converse.
\end{proof}

\begin{Proposition}
\label{prop:Npairs}
For every $k\ge1$, $N(2k+1)=N(2k)$, and $4\mid N(J)$ for every $J\ge4$.
\end{Proposition}
\begin{proof}
Let $k\ge1$. For $T\subseteq\{1,\dots,2k+1\}$ put $U=T\setminus\{2k+1\}$ and $\sigma_U=\sum_{j\in U}j2^j$. Since $(2k+1)2^{2k+1}\equiv2^{2k+1}\pmod{2^{2k+2}}$, the condition $\sum_{j\in T}j2^j\equiv0\pmod{2^{2k+2}}$ is $\sigma_U\equiv-[2k+1\in T]\,2^{2k+1}\pmod{2^{2k+2}}$. If $\sigma_U\equiv0\pmod{2^{2k+1}}$, then $\sigma_U$ is congruent to $0$ or to $2^{2k+1}$ modulo $2^{2k+2}$, and exactly one of the two choices for $2k+1\in T$ satisfies the condition; otherwise none does. By Proposition~\ref{prop:Ncount}(1), $N(2k+1)=\#\{U\subseteq\{1,\dots,2k\}:\ \sigma_U\equiv0\pmod{2^{2k+1}}\}=N(2k)$.

Let $k\ge2$. Since $2k\cdot2^{2k}=k2^{2k+1}\equiv0\pmod{2^{2k+1}}$, the element $2k$ does not affect the condition of Proposition~\ref{prop:Ncount}(1) for $J=2k$, so $N(2k)=2Z$ with $Z=\#\{U\subseteq\{1,\dots,2k-1\}:\ \sigma_U\equiv0\pmod{2^{2k+1}}\}$. For such $U$, $1\notin U$, because $2k+1\ge5$ and $\sigma_U\equiv2\pmod8$ when $1\in U$. By Lemma~\ref{lem:sum}, $\sum_{j=2}^{2k-1}j2^j=(2k-2)2^{2k}=(k-1)2^{2k+1}\equiv0\pmod{2^{2k+1}}$, so $U\mapsto\{2,\dots,2k-1\}\setminus U$ maps the sets counted by $Z$ to themselves; it is an involution without fixed points because $\{2,\dots,2k-1\}\neq\emptyset$. Hence $Z$ is even and $4\mid N(2k)$; with $N(2k+1)=N(2k)$ this gives $4\mid N(J)$ for all $J\ge4$.
\end{proof}

The recursion of Theorem~\ref{thm:step} organizes all states into a forest. For a state $(J,w)$ with $w\ge1$ that does not fail, let $\Phi(J,w)=(J-s,\,2^sw+s-J-1)$, with $s$ as in Theorem~\ref{thm:step}; by that theorem, $\Phi(J,w)$ is a state. We call $(J,w)$ a \emph{root} if $w=0$ or if $(J,w)$ fails. For $J\ge1$ let $F(J)$ be the number of states $(J,w)$ that fail.

\begin{Theorem}
\label{thm:forest}
\begin{enumerate}
\item A state $(J,w)$ with $w\ge1$ fails if and only if $w=(J+1-\sigma)/2^{\sigma-1}$ for some integer $\sigma\ge2$ with $2^{\sigma-1}\mid J+1-\sigma$ and $J+1-\sigma\ge2^{\sigma-1}$. Distinct $\sigma$ give distinct $w$, so $F(J)$ is the number of such $\sigma$, and for every $L\ge1$,
\[
\sum_{J=1}^{L}F(J)=\sum_{\sigma=2}^{L}\Bigl\lfloor\frac{L+1-\sigma}{2^{\sigma-1}}\Bigr\rfloor.
\]
\item Let $(J',w')$ be a state and $m=v_2(J'+1+w')$. The states $(J,w)$ with $w\ge1$ that do not fail and satisfy $\Phi(J,w)=(J',w')$ are exactly the $m$ states $\bigl(J'+\sigma,\,(J'+1+w')/2^{\sigma}\bigr)$, $1\le\sigma\le m$.
\item The map $\Phi$ makes the set of states a forest whose roots are the states $(J,0)$, $J\ge1$, and the failing states; a state is successful if and only if the root of its tree is a state $(J,0)$. For every $J\ge2$,
\[
N(J)=1+\sum_{\sigma=1}^{J-1}\#\bigl\{w'\in S_{J-\sigma}:\ 2^{\sigma}\mid J-\sigma+1+w'\bigr\},\qquad J=1+F(J)+\sum_{\sigma=1}^{J-1}\#\bigl\{0\le w'\le J-\sigma-1:\ 2^{\sigma}\mid J-\sigma+1+w'\bigr\}.
\]
\item The initial states $(K-1,2^h-K)$, $K\in(2^{h-1},2^h]$, are exactly the states $(J,w)$ with $J+1+w=2^h$.
\end{enumerate}
\end{Theorem}
\begin{proof}
(1) By Theorem~\ref{thm:step}, $(J,w)$ fails if and only if $2^{s-1}w+s=J+1$ for the least admissible $s$. Conversely, suppose $2^{\sigma-1}w+\sigma=J+1$ for some $\sigma\ge2$. The function $\tau\mapsto2^\tau w+\tau$ is increasing; at $\tau=\sigma-1$ its value is $J<J+1$, and at $\tau=\sigma$ it is $2(J+1-\sigma)+\sigma=2J+2-\sigma\ge J+1$, because $J+1=2^{\sigma-1}w+\sigma>\sigma$. Hence $\sigma$ is the least admissible value and the state fails. Therefore $(J,w)$ with $w\ge1$ fails if and only if $w=(J+1-\sigma)/2^{\sigma-1}$ for some $\sigma\ge2$, this quotient being an integer at least $1$; such a $w$ satisfies $w\le(J-1)/2\le J-1$, so $(J,w)$ is a state. The quotient is strictly decreasing in $\sigma$, so distinct $\sigma$ give distinct $w$. Finally, for fixed $\sigma\ge2$, the integers $J\le L$ with $J+1-\sigma=2^{\sigma-1}t$, $t\ge1$, correspond to $1\le t\le(L+1-\sigma)/2^{\sigma-1}$, and there are none when $\sigma>L$; summing over $\sigma$ gives the formula.

(2) Put $u=J'+1+w'$; since $0\le w'\le J'-1$, $J'+1\le u\le2J'$. If $\Phi(J,w)=(J',w')$ with step $s$, then $J=J'+s$ and $2^sw=w'+J+1-s=u$, so $2^s\mid u$, $s\le m$ and $w=u/2^s$. Conversely, let $1\le\sigma\le m$, $J=J'+\sigma$ and $w=u/2^\sigma$. Then $w\ge1$, and $w\le u/2\le J'\le J-1$, so $(J,w)$ is a state. We have $2^\sigma w+\sigma=u+\sigma=J+1+w'\ge J+1$, and $2^{\sigma-1}w+\sigma-1=u/2+\sigma-1<J+1$, since this is equivalent to $w'<J'+3$; so $\sigma$ is the least admissible value. The failure condition $2^{\sigma-1}w+\sigma=J+1$ would mean $u=2J'+2$, that is $w'=J'+1$, which is impossible. Finally $2^\sigma w+\sigma-J-1=u+\sigma-J'-\sigma-1=w'$, so $\Phi(J,w)=(J',w')$.

(3) $\Phi$ decreases $J$, so the orbit of every state ends at a root after finitely many steps, and every state that is not a root has exactly one image; this is a forest with the stated roots. By Theorem~\ref{thm:step}, a state is successful if and only if its orbit ends at a state $(J,0)$. The states of level $J$ are $(J,0)$, the $F(J)$ failing states, and the states $(J,w)$ with $w\ge1$ that do not fail; by part (2), the latter correspond bijectively to the pairs $(\sigma,w')$ with $1\le\sigma\le J-1$, $(J-\sigma,w')$ a state and $2^\sigma\mid J-\sigma+1+w'$, through $(J,w)\mapsto(s,\Phi(J,w))$. Such a state is successful if and only if $w'\in S_{J-\sigma}$. Counting the successful states and all states of level $J$ gives the two identities.

(4) If $J=K-1$ and $w=2^h-K$, then $J+1+w=2^h$. Conversely, if $J+1+w=2^h$ with $0\le w\le J-1$, put $K=J+1$; then $K=2^h-w\le2^h$ and $2^h\le2J<2K$, so $K\in(2^{h-1},2^h]$ and $w=2^h-K$.
\end{proof}

By Theorem~\ref{thm:forest}(1), the number of failing states up to level $L$ is at most $\sum_{\sigma\ge2}L/2^{\sigma-1}=L$, and there is exactly one root $(J,0)$ at each level. By Theorem~\ref{thm:forest}(2), the number of children of a state $(J',w')$ is $v_2(J'+1+w')$. Consequently, by parts (3) and (4), an exponent $a$ with candidate $K$ belongs to $\mathcal{A}$ if and only if the state $(K-1,2^{h(K)}-K)$, the unique state of level $K-1$ with $J+1+w$ a power of $2$, lies in the tree of a root $(J,0)$.

\begin{Proposition}
\label{prop:roots}
Let $(J,w)$ be a successful state with $w\ge1$, and let $T\subseteq\{1,\dots,J\}$ be the set representing $2^{J+1}w$. Then $1\notin T$, and the root of the tree of $(J,w)$ is $(\min T-1,0)$. For every $J\ge2$, exactly $N(J)/2$ of the successful states of level $J$ lie in the tree of the root $(1,0)$; in particular $N(J)$ is even.
\end{Proposition}
\begin{proof}
Since $J+1\ge3$, $2^{J+1}w\equiv0\pmod8$, so $1\notin T$, as in the proof of Theorem~\ref{thm:equiv}. By the proof of Theorem~\ref{thm:step} and Lemma~\ref{lem:greedy}, if $j=\max T$ then $\Phi(J,w)=(j-1,w')$, where $T\setminus\{j\}$ represents $2^{j}w'$. Applying this repeatedly removes the elements of $T$ from the largest to the smallest; when the smallest element $\min T$ is removed, the remaining set is empty, the state reached is $(\min T-1,0)$, and $\min T-1\ge1$. Hence the root is $(\min T-1,0)$. Now let $J\ge2$. The successful state $(J,0)$ is represented by $T=\emptyset$ and is its own root, different from $(1,0)$. A successful state of level $J$ therefore lies in the tree of $(1,0)$ if and only if its representing set $T$ satisfies $\min T=2$, that is $2\in T$, since $1\notin T$. The map $T\mapsto\{2,\dots,J\}\setminus T$ of the proof of Proposition~\ref{prop:symmetry} is a bijection of the set of representing sets of the states in $S_J$ onto itself which exchanges the sets containing $2$ and the sets not containing $2$. Hence exactly half of the $N(J)$ successful states have $2\in T$.
\end{proof}

The sets $S_J$ can also be built from the smallest elements of $T$ upwards.

\begin{Theorem}
\label{thm:bottomup}
We have $S_1=\{0\}$, and for every $J\ge2$:
\begin{enumerate}
\item if $J$ is odd, $S_J=\{c/2:\ c\in S_{J-1},\ c\text{ even}\}\cup\{(c+J)/2:\ c\in S_{J-1},\ c\text{ odd}\}$, and $c\mapsto w$ is a bijection from $S_{J-1}$ onto $S_J$;
\item if $J$ is even, $S_J=\{c/2:\ c\in S_{J-1},\ c\text{ even}\}\cup\{c/2+J/2:\ c\in S_{J-1},\ c\text{ even}\}$, and the two sets are disjoint.
\end{enumerate}
Consequently, $N(J)=N(J-1)$ for odd $J$, $N(J)=2\,\#\{c\in S_{J-1}:\ c\text{ even}\}$ for even $J$, and for even $J$ and $0\le w<J/2$, $w\in S_J$ if and only if $w+J/2\in S_J$.
\end{Theorem}
\begin{proof}
$S_1=\{0\}$ because $\mathcal{E}_1=\{0,2\}$ and $4\nmid2$. Let $J\ge2$. By Proposition~\ref{prop:Ncount}(1) and its proof, $w\in S_J$ if and only if $2^{J+1}w=\sum_{j\in T}j2^j$ for a set $T\subseteq\{1,\dots,J\}$, which is then unique. Write $x=1$ if $J\in T$ and $x=0$ otherwise, and $U=T\setminus\{J\}$. If $w\in S_J$, then $\sum_{j\in U}j2^j=2^{J+1}w-xJ2^J\equiv0\pmod{2^J}$, so $c=2^{-J}\sum_{j\in U}j2^j\in S_{J-1}$ and
\[
w=\frac{c+xJ}{2}.
\]
Conversely, if $c\in S_{J-1}$, $x\in\{0,1\}$ and $c+xJ$ is even, then $U\cup\{J\}$ (if $x=1$) or $U$ (if $x=0$), where $U$ represents $2^Jc$, represents $2^{J+1}(c+xJ)/2$, so $(c+xJ)/2\in S_J$. If $J$ is odd, $c+xJ$ is even exactly for $x\equiv c\pmod2$, which gives (1); the map $c\mapsto w$ is injective because $w$ determines $T$, hence $U$ and $c$. If $J$ is even, $c+xJ$ is even exactly when $c$ is even, with both $x=0$ and $x=1$, which gives (2); since $c\le J-2$, $c/2<J/2\le c'/2+J/2$ for all even $c,c'\in S_{J-1}$, so the two sets are disjoint. The consequences follow at once: for even $J$, $S_J=B\cup(B+J/2)$ with $B=\{c/2:\ c\in S_{J-1},\ c\text{ even}\}\subseteq[0,J/2)$.
\end{proof}

Theorem~\ref{thm:bottomup} gives a second proof of the equality $N(2k+1)=N(2k)$ of Proposition~\ref{prop:Npairs}. In terms of Theorem~\ref{thm:bottomup}, an exponent $a$ with candidate $K$ belongs to $\mathcal{A}$ if and only if $2^{h(K)}-K\in S_{K-1}$, where the sets $S_J$ are obtained from $S_1=\{0\}$ by the maps $c\mapsto c/2$ and $c\mapsto(c+J)/2$ of parts (1) and (2).

The symmetry of Proposition~\ref{prop:symmetry} transports the states decided by one step of the recursion to further initial states. The first family below is the formula $c(2^k-1)=k2^{k-1}$ of~\cite{nicolas2005open} at $k=2^r$.

\begin{Theorem}
\label{thm:symfamilies}
\begin{enumerate}
\item For every $r\ge0$, $c(2^{2^r}-1)=2^{2^r+r-1}$; the candidate of the exponent $2^r+r-1$ is $K=2^r+1$.
\item Let $i\ge1$, $\sigma=2^{i-1}+1$, and let $h\ge\sigma+2$ with $h\equiv i\pmod{\sigma+1}$. Then $w=(2^h-2\sigma+2)/(2^{\sigma+1}-1)$ is an even positive integer, $K=2^{h-1}+1+w/2$ satisfies $2^{h-1}+1<K<2^h$, and $K+h-3\in\mathcal{A}$.
\item Let $i\ge2$, $\sigma=2^{i-1}+1$, and let $h\ge\sigma+1$ with $h\equiv i\pmod{\sigma}$. Then $w=(2^h-2\sigma+2)/(2^{\sigma}-1)$ is an even positive integer, $K=2^{h-1}+1+w/2$ satisfies $2^{h-1}+1<K<2^h$, and $K+h-3\notin\mathcal{A}$.
\end{enumerate}
\end{Theorem}
\begin{proof}
(1) By the proof of Lemma~\ref{lem:cformula}, $c(2^k-1)=k2^{k-1}$; take $k=2^r$. Then $\mathcal{B}(2^k-1)+2=\{2,\dots,k+1\}$, whose largest element is $K=2^r+1$.

(2) Put $M=2^{\sigma+1}-1$. Since $2^{\sigma+1}\equiv1\pmod M$ and $h\equiv i\pmod{\sigma+1}$, $2^h\equiv2^i=2\sigma-2\pmod M$, so $w$ is an integer; and $w\ge1$ because $2^h\ge2^{\sigma+2}=2M+2>M+2\sigma-2$. Put $J'=2^\sigma w-1\ge1$ and $J=J'+\sigma$. Since $v_2(J'+1)\ge\sigma$, Theorem~\ref{thm:forest}(2) shows that $(J,w)$ is a state that does not fail, with $\Phi(J,w)=(J',0)$; hence $w\in S_J$, and $J-1-w\in S_J$ by Proposition~\ref{prop:symmetry}. Moreover $2J-w=2^{\sigma+1}w+2\sigma-2-w=Mw+2\sigma-2=2^h$, so $w$ is even and, with $K=J+1$, $K=2^{h-1}+1+w/2$ and $2^h-K=J-1-w\in S_{K-1}$. Since $w\ge2$ and $w<2^h-2$, $2^{h-1}+1<K<2^h$, so $h=h(K)$, and Theorem~\ref{thm:leading} gives $K+h-3\in\mathcal{A}$.

(3) Put $M'=2^{\sigma}-1$. As in (2), $2^h\equiv2^i=2\sigma-2\pmod{M'}$, so $w$ is an integer, and $w\ge1$ because $2^h\ge2^{\sigma+1}=2M'+2\ge M'+2\sigma-2$ for $\sigma\ge3$. Put $J=2^{\sigma-1}w+\sigma-1$. Then $J+1-\sigma=2^{\sigma-1}w\ge2^{\sigma-1}$ and $w=(J+1-\sigma)/2^{\sigma-1}$, so the state $(J,w)$ fails by Theorem~\ref{thm:forest}(1), and $w\notin S_J$; by Proposition~\ref{prop:symmetry}, $J-1-w\notin S_J$. Moreover $2J-w=2^\sigma w+2\sigma-2-w=M'w+2\sigma-2=2^h$, and the conclusion follows as in (2).
\end{proof}

\begin{Theorem}
\label{thm:counting2}
As $x\to\infty$,
\[
A(x)\ge(3+C_1)\log_2x-O(\log\log x),\qquad B(x)\ge\Bigl(\frac54+\frac E2+C_2\Bigr)\log_2x-O(\log\log x),
\]
where $C_1=\sum_{k\ge0}1/(2^k+2)=0.9655832\ldots$, $C_2=\sum_{k\ge1}1/(2^k+1)=0.7644997\ldots$ and $E$ is as in Theorem~\ref{thm:counting}; thus $3+C_1=3.9655832\ldots$ and $\frac54+\frac E2+C_2=2.8178473\ldots$.
\end{Theorem}
\begin{proof}
We keep the notation $H=\lfloor\log_2x\rfloor-1$ of the proof of Theorem~\ref{thm:counting}, whose families we use together with those of Theorem~\ref{thm:symfamilies}. All the exponents are of the form $\beta(K)-3$ with $K\le2^h$, $h\le H$, hence at most $x$, and distinct values of $K$ give distinct exponents. For $h\ge4$, the integers $K$ of Theorem~\ref{thm:symfamilies}(2) and~(3) satisfy $K=2^{h-1}+1+w/2$ with $w\le2^h/7$, hence $K<\frac23\,2^h$ because $2^{h-1}(\frac13-\frac17)>1$; the integers $K$ of Theorems~\ref{thm:members}(2) and~\ref{thm:nonmembers} satisfy $K>2^h-2^h/3=\frac23\,2^h$, since there the denominators $2^s+1$ and $2^{s-1}+1$ are at least $3$. In Theorem~\ref{thm:symfamilies}(2) and~(3), $w/2$ is strictly decreasing in $\sigma$, and $K>2^{h-1}+1$; and for $h\ge3$ the integer $2^{h-1}+1$ of Theorem~\ref{thm:symfamilies}(1) differs from $2^h$ and from the integers of Theorem~\ref{thm:members}(2), which exceed $\frac23\,2^h$. Hence, for $h\ge4$, all the integers $K$ produced in the block $(2^{h-1},2^h]$ are distinct.

Members. Besides the $2H-\log_2H-3$ exponents of the proof of Theorem~\ref{thm:counting}, Theorem~\ref{thm:symfamilies}(1) gives one exponent for each $4\le h\le H$, and Theorem~\ref{thm:symfamilies}(2) gives, for each $1\le i\le\kappa=\lfloor\log_2H\rfloor$, at least $(H-\sigma-1)/(\sigma+1)-1$ integers $h\in[\sigma+2,H]$ with $h\equiv i\pmod{\sigma+1}$, where $\sigma=2^{i-1}+1$. Since $\sum_{i>\kappa}1/(2^{i-1}+2)\le2^{1-\kappa}<4/H$ and $\sigma\le H/2+1$ for $i\le\kappa$, the sum over $i$ is at least $C_1H-O(\log H)$.

Non-members. Besides the exponents of the proof of Theorem~\ref{thm:counting}, Theorem~\ref{thm:symfamilies}(3) gives, for each $2\le i\le\kappa$, at least $(H-\sigma)/\sigma-1$ integers $h\in[\sigma+1,H]$ with $h\equiv i\pmod\sigma$; as above, the sum over $i$ is at least $\bigl(\sum_{i\ge2}1/(2^{i-1}+1)\bigr)H-O(\log H)=C_2H-O(\log H)$. Since $H=\log_2x+O(1)$, the bounds follow.
\end{proof}

\section{The analogue for an arbitrary prime}
\label{sec:primes}
Let $p$ be a prime and $v_p$ the $p$-adic valuation. Put
\[
c_p(n)=\sum_{k=1}^{n}p^{v_p(k)},\qquad \mathcal{A}_p=\{a\ge0:\ p^a\in c_p(\mathbb{N})\},\qquad A_p(x)=\#\{a\in\mathcal{A}_p:\ a\le x\},
\]
and $B_p(x)=\#\{a\in\mathbb{Z}\cap[0,x]:\ a\notin\mathcal{A}_p\}$, so that $c_2=c$, $\mathcal{A}_2=\mathcal{A}$, $A_2=A$ and $B_2=B$. The interpretation of $c$ recalled in Section~\ref{sec:intro} extends to every prime.

\begin{Proposition}
\label{prop:Fp}
For every $n\ge1$, $c_p(n)$ is the exponent of $1-X$ in the factorization of $(1-X)(1-X^2)\cdots(1-X^n)$ into irreducible factors over $\mathbb{F}_p[X]$.
\end{Proposition}
\begin{proof}
Write $k=p^vk'$ with $p\nmid k'$. In characteristic $p$, $1-X^k=(1-X^{k'})^{p^v}$, and $1-X^{k'}=(1-X)(1+X+\dots+X^{k'-1})$, where the second factor takes the value $k'\neq0$ at $X=1$; hence $1-X$ divides $1-X^k$ exactly $p^v=p^{v_p(k)}$ times, and the exponents add up over $k\le n$.
\end{proof}

\begin{Lemma}
\label{lem:cp}
\begin{enumerate}
\item For every $n\ge1$, $c_p(pn)=p\,c_p(n)+(p-1)n$.
\item For every $m\ge0$, $c_p(p^m-1)=m(p-1)p^{m-1}$ and $c_p(p^m)=p^{m-1}\bigl((p-1)m+p\bigr)$.
\item If $n=\sum_{i\ge0}d_ip^i$ is the expansion of $n$ in base $p$, then $c_p(n)=\sum_{i\ge0}d_i\,p^{i-1}\bigl((p-1)i+p\bigr)$.
\end{enumerate}
\end{Lemma}
\begin{proof}
(1) Among $k\le pn$, the $(p-1)n$ integers prime to $p$ contribute $1$ each, and $k=pk_1$ with $k_1\le n$ contributes $p\cdot p^{v_p(k_1)}$. (2) For $0\le v\le m-1$, exactly $(p-1)p^{m-1-v}$ integers $k\in[1,p^m-1]$ have $v_p(k)=v$, which gives $c_p(p^m-1)$, and $c_p(p^m)=c_p(p^m-1)+p^m$. (3) Let $m\ge0$, $1\le d\le p-1$ and $0\le s<p^m$. For $0\le t\le d-1$ and $1\le k\le p^m-1$, $v_p(tp^m+k)=v_p(k)$, and $v_p(tp^m)=m$ for $1\le t\le d$; hence $c_p(dp^m+s)=d\bigl(c_p(p^m-1)+p^m\bigr)+c_p(s)=d\,c_p(p^m)+c_p(s)$, with $c_p(0)=0$. Induction on the number of nonzero digits and (2) give (3).
\end{proof}

For $p=2$, part (1) is the recurrence $c(2n)=2c(n)+n$ of~\cite{nicolas2005open}, and part (3) is Lemma~\ref{lem:cformula}. Put $t_i=p\,c_p(p^i)=p^i\bigl((p-1)i+p\bigr)$ for $i\ge0$, and let $\mathcal{E}^{(p)}_K$ be the set of sums $\sum_{0\le i<K}d_it_i$ with $0\le d_i\le p-1$.

\begin{Theorem}
\label{thm:primes}
\begin{enumerate}
\item For $a\ge0$, $a\in\mathcal{A}_p$ if and only if $p^{a+1}=\sum_{i\ge0}d_it_i$ with $0\le d_i\le p-1$, not all zero; then $n=\sum_id_ip^i$ satisfies $c_p(n)=p^a$.
\item For every $m\ge0$, $\sum_{0\le i<m}(p-1)t_i=m(p-1)p^m<t_m$. Hence a representation $V=\sum_id_it_i$ with digits $0\le d_i\le p-1$ is unique, and its largest index $K$ with $d_K\neq0$ satisfies $d_K=\lfloor V/t_K\rfloor$.
\item For $K\ge0$ let $g(K)$ be the least integer $g\ge1$ with $p^g\ge(p-1)(K+1)+1$. If $p^{b}=\sum_id_it_i$ has largest index $K$, then $b=K+g(K)$ and $d_K=\lfloor p^{g(K)}/((p-1)K+p)\rfloor\in[1,p-1]$. The map $K\mapsto K+g(K)$ is strictly increasing on $\{0,1,2,\dots\}$, and the integers $b\ge1$ outside its image are exactly $b=(p^g-1)/(p-1)+g$, $g\ge1$. Consequently, $a\notin\mathcal{A}_p$ for $a=(p^g-1)/(p-1)+g-1$, $g\ge1$, and every other $a\ge0$ has a unique candidate $K$ with $K+g(K)=a+1$.
\end{enumerate}
\end{Theorem}
\begin{proof}
(1) By Lemma~\ref{lem:cp}(3), $p\,c_p(n)=\sum_id_it_i$, and every digit vector with digits in $[0,p-1]$, not all zero, is the expansion of a unique $n\ge1$.

(2) By Lemma~\ref{lem:cp}(2), $\sum_{i<m}(p-1)t_i=p\,c_p(p^m-1)=m(p-1)p^m<p^m((p-1)m+p)=t_m$. If $K$ is the largest index with $d_K\neq0$, then $0\le V-d_Kt_K\le\sum_{i<K}(p-1)t_i<t_K$, so $d_K=\lfloor V/t_K\rfloor$; uniqueness follows by induction.

(3) Put $u=(p-1)(K+1)$ and $\gamma=b-K$. From $t_K\le p^b\le\sum_{i\le K}(p-1)t_i=(K+1)(p-1)p^{K+1}$ we get $u+1=(p-1)K+p\le p^\gamma\le pu$. The interval $[u+1,pu]$ contains exactly one power of $p$: if $g$ is least with $p^g\ge u+1$, then $g\ge1$ because $u+1\ge p$, and $p^{g-1}\le u$, so $p^g\le pu$; and $p^{g+1}>pu$. Hence $\gamma=g(K)$. Since $p^{g(K)}\le pu<p((p-1)K+p)$ and $p^{g(K)}\ge(p-1)K+p$, part (2) gives $1\le d_K\le p-1$. Next, $u$ increases by $p-1$ when $K$ increases by $1$, so $g(K+1)-g(K)\in\{0,1\}$, and $g(K+1)=g(K)+1$ exactly when $p^{g(K)}<(p-1)(K+2)+1$, that is $p^{g(K)}-1\in[u,u+p-2]$. Both $p^{g}-1$ and $u$ are multiples of $p-1$, so this means $p^{g(K)}-1=u$, that is $K+1=(p^{g}-1)/(p-1)$ with $g=g(K)$. Hence $K\mapsto K+g(K)$ increases by $1$ at each step except from $K=(p^g-1)/(p-1)-1$, where $g(K)=g$, to $K+1$, where it increases by $2$ and skips $b=K+g+1=(p^g-1)/(p-1)+g$; every $g\ge1$ occurs, and $0+g(0)=1$. The last statement follows from (1) with $b=a+1$.
\end{proof}

For $p=2$, the change of index $j=i+2$ turns $t_i$ into $j2^j/4$; the candidate of Theorem~\ref{thm:primes} is the candidate of Theorem~\ref{thm:leading} minus $2$, and the excluded exponents are $2^g+g-2$. The recursion of Theorem~\ref{thm:step} extends to every prime as follows. A \emph{$p$-state} is a pair $(K,w)$ of integers with $K\ge0$ and $0\le w\le(p-1)K$; it is \emph{successful} if $p^Kw\in\mathcal{E}^{(p)}_K$.

\begin{Theorem}
\label{thm:primestep}
\begin{enumerate}
\item Let $a\ge0$ have the candidate $K$, put $g=a+1-K$, $u=(p-1)K+p$, $d=\lfloor p^g/u\rfloor$ and $w_0=p^g-du$. Then $a\in\mathcal{A}_p$ if and only if $w_0\le(p-1)K$ and the $p$-state $(K,w_0)$ is successful.
\item A $p$-state $(K,0)$ is successful. Let $(K,w)$ be a $p$-state with $w\ge1$, so $K\ge1$; let $s$ be the least integer $\sigma\ge1$ with $p^\sigma w\ge(p-1)(K-\sigma)+p$, put $i=K-s$, $u_i=(p-1)i+p$, $d=\lfloor p^sw/u_i\rfloor$ and $w'=p^sw-du_i$. Then $1\le s\le K$, and $(K,w)$ is successful if and only if $d\le p-1$, $w'\le(p-1)i$, and the $p$-state $(i,w')$ is successful.
\end{enumerate}
\end{Theorem}
\begin{proof}
(1) By Theorem~\ref{thm:primes}, $a\in\mathcal{A}_p$ if and only if $p^{a+1}=dt_K+R$ with $R\in\mathcal{E}^{(p)}_K$, where $d=\lfloor p^{a+1}/t_K\rfloor$; here $R=p^K(p^g-du)=p^Kw_0$, and $R\le\max\mathcal{E}^{(p)}_K=(p-1)Kp^K$ means $w_0\le(p-1)K$.

(2) Let $V=p^Kw\ge1$. For $0\le i'<K$, $t_{i'}\le V$ is equivalent to $(p-1)i'+p\le p^{K-i'}w$, so $i=K-s$ is the largest index below $K$ with $t_i\le V$; $s\le K$ because $p^Kw\ge p$. By Theorem~\ref{thm:primes}(2), a representation of $V$ in $\mathcal{E}^{(p)}_K$ has largest index $i$ and digit $\lfloor V/t_i\rfloor=d$: indeed its largest index $m$ satisfies $t_m\le V$, so $m\le i$, and $m<i$ is impossible because $V\le\sum_{i'\le m}(p-1)t_{i'}<t_{m+1}\le t_i\le V$. Hence $V\in\mathcal{E}^{(p)}_K$ if and only if $d\le p-1$ and $V-dt_i=p^iw'\in\mathcal{E}^{(p)}_i$; the latter requires $p^iw'\le(p-1)ip^i$, that is $w'\le(p-1)i$.
\end{proof}

Since $s\ge1$, the index decreases at each step, so the recursion ends after at most $K$ steps; by the minimality of $s$, $p^{s-1}w<(p-1)(i+1)+p$, so all the integers involved are $O(pK)$. For an odd prime, the condition $w_0\le(p-1)K$ in part (1) can fail, which never happens for $p=2$; this gives a family of non-members with no analogue for $p=2$.

\begin{Theorem}
\label{thm:primefamilies}
Let $p$ be a prime.
\begin{enumerate}
\item For every $g\ge1$, $K=(p^g-p)/(p-1)$ satisfies $c_p(p^K)=p^{K+g-1}$; thus $K+g-1\in\mathcal{A}_p$.
\item If $p$ is odd, then $c_p(p^m-1)$ is not a power of $p$ for any $m\ge1$.
\item If $p$ is odd and $g\ge2$ is even, then $K=(p^g-2p+1)/(2(p-1))$ is a nonnegative integer with candidate exponent $K+g-1$, and $K+g-1\notin\mathcal{A}_p$.
\end{enumerate}
Consequently, for every odd prime $p$, $A_p(x)\ge\log_px-O(1)$ and $B_p(x)\ge\frac32\log_px-O(1)$.
\end{Theorem}
\begin{proof}
(1) $(p-1)K+p=p^g$, so $c_p(p^K)=p^{K-1}p^g$ by Lemma~\ref{lem:cp}(2). (2) $c_p(p^m-1)=m(p-1)p^{m-1}$, and $m(p-1)$ is not a power of $p$ because $p-1\ge2$ divides it and is prime to $p$. (3) Since $p^2-1=(p-1)(p+1)$ and $p+1$ is even, $p^2\equiv1\pmod{2(p-1)}$, so $p^g\equiv1$ and $p^g-2p+1\equiv2-2p\equiv0\pmod{2(p-1)}$; and $p^g\ge p^2>2p-1$, so $K\ge0$. Put $u=(p-1)K+p=(p^g+1)/2$. Then $u=(p-1)(K+1)+1\le p^g$ and $p^g\le p(u-1)=p(p^g-1)/2$ because $p\ge3$, so $g(K)=g$ by the proof of Theorem~\ref{thm:primes}(3), and $K+g-1$ has candidate $K$. Moreover $d=\lfloor p^g/u\rfloor=\lfloor2p^g/(p^g+1)\rfloor=1$ and $w_0=p^g-u=u-1=(p-1)K+p-1>(p-1)K$, so $K+g-1\notin\mathcal{A}_p$ by Theorem~\ref{thm:primestep}(1).

For the counting statement, the exponents of (1), of (3) and of Theorem~\ref{thm:primes}(3) are at most $p^{g}/(p-1)+g$ for the corresponding $g$, so those with $g\le\log_px-1$ are at most $x$ for large $x$; there are $\log_px-O(1)$ values of $g$ in (1) and in Theorem~\ref{thm:primes}(3), and $\frac12\log_px-O(1)$ even values in (3). Members and non-members are distinct, the exponents of Theorem~\ref{thm:primes}(3) have no candidate, and distinct $g$ give distinct $K$ and hence, by Theorem~\ref{thm:primes}(3), distinct exponents.
\end{proof}

For $p=3$, Theorem~\ref{thm:primefamilies} gives $c_3(27)=81$, so $4\in\mathcal{A}_3$, and $2\notin\mathcal{A}_3$; Theorem~\ref{thm:primes}(3) gives $1\notin\mathcal{A}_3$; and $c_3(13)=c_3(1)+c_3(3)+c_3(9)=1+5+21=27$, so $3\in\mathcal{A}_3$.

The exponents rejected by the condition $w_0\le(p-1)K$ of Theorem~\ref{thm:primestep}(1), which we call \emph{immediate failures}, admit a complete description.

\begin{Theorem}
\label{thm:immediate}
Let $a\ge0$ have the candidate $K$, and put $g=a+1-K$ and $u=(p-1)K+p$. Then $a$ is an immediate failure if and only if $u\mid p^g+j$ for some $j\in\{1,\dots,p-1\}$; in that case $e=(p^g+j)/u$ satisfies $2\le e\le p-1$. Consequently, there are no immediate failures for $p=2$; for $p=3$ the immediate failures are exactly the exponents of Theorem~\ref{thm:primefamilies}(3); and for every prime $p$ the immediate failures are the exponents $K+g-1$ obtained from the triples $(g,e,j)$ with $2\le e\le p-1$, $1\le j\le p-1$, $e\mid p^g+j$, $u=(p^g+j)/e\equiv1\pmod{p-1}$, $u\ge p$ and $u\le p^g\le p(u-1)$, through $K=(u-p)/(p-1)$. In particular, there are at most $(p-1)(p-2)$ immediate failures with a given $g$.
\end{Theorem}
\begin{proof}
By the proof of Theorem~\ref{thm:primes}(3), $u\le p^g\le p(u-1)$, $d=\lfloor p^g/u\rfloor\in[1,p-1]$ and $0\le w_0=p^g-du<u$. Hence $w_0>(p-1)K=u-p$ if and only if $w_0=u-j$ with $1\le j\le p-1$, that is $p^g+j=(d+1)u$, which is $u\mid p^g+j$ because $0\le w_0<u$ determines $d$. Then $e=d+1\ge2$, and $e\le p-1$ because $p^g+j\le p(u-1)+p-1<pu$. For $p=2$ the range $2\le e\le p-1$ is empty. Conversely, given a triple as in the statement, $K=(u-p)/(p-1)$ is a nonnegative integer with $(p-1)K+p=u$, the inequalities $u\le p^g\le p(u-1)$ say that $g=g(K)$, so $K+g-1$ has candidate $K$, and $p^g=eu-j$ with $1\le j\le p-1<u$ gives $d=e-1$ and $w_0=u-j>u-p$. For $p=3$, $e=2$ and $j\in\{1,2\}$; $2\mid3^g+j$ forces $j=1$, and $u=(3^g+1)/2$ is odd, that is $u\equiv1\pmod2$, exactly when $3^g\equiv1\pmod4$, that is $g$ even; this is Theorem~\ref{thm:primefamilies}(3). For given $g$, each pair $(e,j)$ gives at most one $u$, hence at most one exponent.
\end{proof}

The sets of successful $p$-states satisfy the analogues of Proposition~\ref{prop:symmetry} and Theorem~\ref{thm:bottomup}. For $K\ge0$ let $S^{(p)}_K$ be the set of $w$ such that $(K,w)$ is a successful $p$-state, and $N_p(K)=|S^{(p)}_K|$; let $u_K=(p-1)K+p$.

\begin{Theorem}
\label{thm:primebottomup}
\begin{enumerate}
\item $S^{(p)}_0=\{0\}$, and for every $K\ge0$, $S^{(p)}_{K+1}=\{(w+du_K)/p:\ w\in S^{(p)}_K,\ 0\le d\le p-1,\ p\mid w+du_K\}$, the elements obtained from distinct pairs $(w,d)$ being distinct.
\item If $p\nmid K$, then for each $w\in S^{(p)}_K$ exactly one $d\in\{0,\dots,p-1\}$ satisfies $p\mid w+du_K$, and $N_p(K+1)=N_p(K)$.
\item If $p\mid K$, then $S^{(p)}_{K+1}=\bigcup_{d=0}^{p-1}\bigl(B+d\,u_K/p\bigr)$ with $B=\{w/p:\ w\in S^{(p)}_K,\ p\mid w\}$, the $p$ sets being disjoint; thus $N_p(K+1)=p\,\#\{w\in S^{(p)}_K:\ p\mid w\}$.
\item For every $K\ge0$, $w\in S^{(p)}_K$ if and only if $(p-1)K-w\in S^{(p)}_K$.
\end{enumerate}
An exponent $a$ with candidate $K$ belongs to $\mathcal{A}_p$ if and only if $w_0\le(p-1)K$ and $w_0\in S^{(p)}_K$, with $w_0$ as in Theorem~\ref{thm:primestep}(1).
\end{Theorem}
\begin{proof}
(1) $\mathcal{E}^{(p)}_0=\{0\}$ gives $S^{(p)}_0=\{0\}$. By Theorem~\ref{thm:primes}(2), $p^{K+1}w'\in\mathcal{E}^{(p)}_{K+1}$ if and only if $p^{K+1}w'=dt_K+p^Kw$ with $0\le d\le p-1$ and $p^Kw\in\mathcal{E}^{(p)}_K$; since $t_K=p^Ku_K$, this is $pw'=w+du_K$, and $0\le w\le(p-1)K$ holds for every element $p^Kw$ of $\mathcal{E}^{(p)}_K$. Distinct pairs $(w,d)$ give distinct representations, hence distinct $w'$ by Theorem~\ref{thm:primes}(2). (2) $u_K\equiv(p-1)K\equiv-K\pmod p$ is invertible modulo $p$ when $p\nmid K$. (3) If $p\mid K$, then $p\mid u_K$, and $p\mid w+du_K$ is $p\mid w$ for all $d$; the sets are disjoint because $B\subseteq[0,(p-1)K/p]$ and $u_K/p=(p-1)K/p+1$. (4) By Lemma~\ref{lem:cp}(2), $\sum_{i<K}(p-1)t_i=(p-1)Kp^K$; replacing every digit $d_i$ by $p-1-d_i$ maps a representation of $p^Kw$ to one of $p^K((p-1)K-w)$. The last statement is Theorem~\ref{thm:primestep}(1).
\end{proof}

For $p=2$, Theorem~\ref{thm:primebottomup} is Theorem~\ref{thm:bottomup} and Proposition~\ref{prop:symmetry} after the change of index of Section~\ref{sec:primes}.

\section{Experiments}
\label{sec:experiments}
All computations of this section were made by the script \texttt{powers\_of\_two\_c.py}, which was written with Claude Opus 5.5 and run by the author with Python 3.12.3, with the parameters $2^{20}$ for the range of the check of Lemma~\ref{lem:cformula}, $2^{24}$ for the brute-force search, $4000$ for the big-integer check, $x\le20000$ for the counting functions, $h\le300$ for the closed-form checks of the families, $h\le18$ for the runs of Algorithm~\ref{alg:membership} on the families, $J\le65536$ for the sets $S_J$ computed with the recursion of Theorem~\ref{thm:step}, and $J\le131072$ for the sets $S_J$ computed with the recursion of Theorem~\ref{thm:bottomup}, with NumPy 2.4.6, $a\le3000$ for the recursion of Theorem~\ref{thm:primestep} with the primes $p=3,5,7,11$, $a\le100000$ for the immediate failures and $K\le10000$ for the recursion of Theorem~\ref{thm:primebottomup}; the whole run took $222.5$ seconds. The script requires Python~3.12 and the Python package NumPy; the run reported here used Python~3.12.3 and NumPy~2.4.6. NumPy is used only for the sets $S_J$ (Sections~\ref{subsec:states-exp}--\ref{subsec:bottomup-exp}); without it the script runs in pure Python with $J\le8192$ and $J\le16384$ for the two recursions. The script uses exact integer arithmetic only. It decides the membership of an exponent $a$ in $\mathcal{A}$ by three independent methods: a brute-force search computing $c(n)$ from the definition~\eqref{eq:cdef}; the greedy algorithm applied to the integers $2^{a+3}$ and $j2^j$ themselves; and Algorithm~\ref{alg:membership}. The script performs $121$ checks, and all of them passed.

\subsection{Verification of the proved statements}
\label{subsec:verification}
The identity~\eqref{eq:cformula} holds for $1\le n\le2^{20}$, the formula $c(2^r)=2^{r-1}(r+2)$ holds for $0\le r<200$, and $c(1),\dots,c(16)$ agree with the table of Section~7 of~\cite{nicolas2005open}. The brute-force search over $1\le n\le2^{24}$ reaches $c(2^{24})=218103808$, so it decides the membership of every exponent $0\le a\le27$. Table~\ref{tab:brute} lists the exponents found, with the integer $n$ such that $c(n)=2^a$. For all $0\le a\le27$, the brute-force search, the big-integer greedy algorithm and Algorithm~\ref{alg:membership} return the same answer, and for the exponents in $\mathcal{A}$ the integer $n=\sum_{j\in T}2^{j-2}$ of Corollary~\ref{cor:algo} equals the integer found by the search.

\begin{table}[H]
\centering
\caption{The exponents $0\le a\le27$ with $2^a\in c(\mathbb{N})$, and the integer $n$ with $c(n)=2^a$, found by the brute-force search over $n\le2^{24}$. The other exponents $a\le27$ are $1,4,6,7,9,18,21,23,24,26,27$.}
\label{tab:brute}
\begin{tabular}{rrrrrrrr}
\toprule
$a$ & $n$ & $a$ & $n$ & $a$ & $n$ & $a$ & $n$\\
\midrule
$0$ & $1$ & $10$ & $255$ & $14$ & $2624$ & $19$ & $65535$\\
$2$ & $3$ & $11$ & $447$ & $15$ & $4864$ & $20$ & $122111$\\
$3$ & $4$ & $12$ & $768$ & $16$ & $8960$ & $22$ & $433407$\\
$5$ & $15$ & $13$ & $1471$ & $17$ & $16384$ & $25$ & $3023616$\\
$8$ & $64$ & & & & & &\\
\bottomrule
\end{tabular}
\end{table}

For $0\le a\le4000$, Algorithm~\ref{alg:membership} and the big-integer greedy algorithm return the same answer, the set $T$ produced by Algorithm~\ref{alg:membership} is the set produced by the greedy algorithm, and for the exponents $a\le1500$ in $\mathcal{A}$ the integer $n$ of Corollary~\ref{cor:algo} satisfies $c(n)=2^a$. The values $3\le b\le5000$ not taken by $\beta$ are $4,7,12,21,38,71,136,265,522,1035,2060,4109$, that is $2^r+r+1$ for $1\le r\le12$, as stated in Theorem~\ref{thm:leading}, and $0\le2^h-K\le K-2$ holds for $2\le K<2^{16}$. For $0\le a\le20000$, Algorithm~\ref{alg:membership} performs at most $K-2$ iterations and handles integers at most $2K$ in its loop, as stated in Corollary~\ref{cor:algo}; the largest number of iterations is $19781$.

For Theorem~\ref{thm:members}(2), the $295$ pairs $(k,h)$ with $h\le300$ give integers $K$ with $2^{h-1}<K<2^h$, $K-s\ge2$ and $K(2^s+1)-s=2^{h+s}$, which is the identity used in the proof of~\eqref{eq:member}; the equality~\eqref{eq:member} itself was evaluated with Lemma~\ref{lem:cformula} for $h\le16$. For Theorem~\ref{thm:nonmembers}, the $310$ pairs $(s,h)$ with $h\le300$ give integers $K$ with $2^{h-1}<K<2^h$, the least $\sigma$ of Theorem~\ref{thm:step} equals $s$, and $2^{s-1}w+s=J+1$. Table~\ref{tab:families} lists the pairs with $h\le18$; on each of them Algorithm~\ref{alg:membership} returns the answer of the theorem, a member for Theorem~\ref{thm:members} and a failure at the first iteration for Theorem~\ref{thm:nonmembers}, and the big-integer greedy algorithm agrees for $a\le4000$. The exponents $a+(2^a-11)/3$ for odd $3\le a\le15$ are in $\mathcal{A}$, the exponents $a+(2^a-10)/3$ for even $4\le a\le14$ are not, and the exponents $2^r+r-2$, $1\le r<40$, have no candidate $K$.

\begin{table}[H]
\centering
\caption{The families of Theorems~\ref{thm:members}(2) and~\ref{thm:nonmembers} with $h\le18$: the parameter $s$, the integer $K$ and the exponent $a=K+h-3$.}
\label{tab:families}
\begin{tabular}{rrrr@{\qquad}rrrr}
\toprule
\multicolumn{4}{c}{Members (Theorem~\ref{thm:members})} & \multicolumn{4}{c}{Non-members (Theorem~\ref{thm:nonmembers})}\\
$s$ & $h$ & $K$ & $a$ & $s$ & $h$ & $K$ & $a$\\
\midrule
$1$ & $2$ & $3$ & $2$ & $2$ & $3$ & $6$ & $6$\\
$1$ & $4$ & $11$ & $12$ & $2$ & $5$ & $22$ & $24$\\
$1$ & $6$ & $43$ & $46$ & $2$ & $7$ & $86$ & $90$\\
$1$ & $8$ & $171$ & $176$ & $2$ & $9$ & $342$ & $348$\\
$1$ & $10$ & $683$ & $690$ & $2$ & $11$ & $1366$ & $1374$\\
$1$ & $12$ & $2731$ & $2740$ & $2$ & $13$ & $5462$ & $5472$\\
$1$ & $14$ & $10923$ & $10934$ & $2$ & $15$ & $21846$ & $21858$\\
$1$ & $16$ & $43691$ & $43704$ & $2$ & $17$ & $87382$ & $87396$\\
$1$ & $18$ & $174763$ & $174778$ & $4$ & $8$ & $228$ & $233$\\
$2$ & $5$ & $26$ & $28$ & $4$ & $14$ & $14564$ & $14575$\\
$2$ & $9$ & $410$ & $416$ & $8$ & $17$ & $130056$ & $130070$\\
$2$ & $13$ & $6554$ & $6564$ & $3$ & $3$ & $7$ & $7$\\
$2$ & $17$ & $104858$ & $104872$ & $3$ & $7$ & $103$ & $107$\\
$4$ & $10$ & $964$ & $971$ & $3$ & $11$ & $1639$ & $1647$\\
$4$ & $18$ & $246724$ & $246739$ & $3$ & $15$ & $26215$ & $26227$\\
\bottomrule
\end{tabular}
\end{table}

\subsection{The counting functions}
\label{subsec:counting-exp}
Table~\ref{tab:counting} gives $A(x)$ and $B(x)$ for $x=1000,2000,\dots,20000$, computed with Algorithm~\ref{alg:membership}. The exponent $a=0$ belongs to $\mathcal{A}$ because $c(1)=1=2^0$, and the number $A(x)-1$ of exponents $1\le a\le x$ in $\mathcal{A}$ coincides with the table of Nicolas~\cite{nicolas2005open} at the ten values $x=1000,\dots,10000$. In the range $x\le20000$ the ratio $A(x)/x$ takes values between $0.5132$, at $x=6000$, and $0.7418$, at $x=20000$, and $B(x)$ increases by $42$ between $x=15000$ and $x=20000$.

\begin{table}[H]
\centering
\caption{The counting functions $A(x)$ and $B(x)$ of~\eqref{eq:Adef}, and the values of the table of Nicolas~\cite{nicolas2005open}, which count the exponents $1\le a\le x$.}
\label{tab:counting}
\begin{tabular}{rrrrr@{\qquad}rrrr}
\toprule
$x$ & $A(x)$ & $B(x)$ & $A(x)/x$ & Nicolas & $x$ & $A(x)$ & $B(x)$ & $A(x)/x$\\
\midrule
$1000$ & $636$ & $365$ & $0.6360$ & $635$ & $11000$ & $6664$ & $4337$ & $0.6058$\\
$2000$ & $1375$ & $626$ & $0.6875$ & $1374$ & $12000$ & $7332$ & $4669$ & $0.6110$\\
$3000$ & $1788$ & $1213$ & $0.5960$ & $1787$ & $13000$ & $8133$ & $4868$ & $0.6256$\\
$4000$ & $2406$ & $1595$ & $0.6015$ & $2405$ & $14000$ & $8939$ & $5062$ & $0.6385$\\
$5000$ & $2749$ & $2252$ & $0.5498$ & $2748$ & $15000$ & $9878$ & $5123$ & $0.6585$\\
$6000$ & $3079$ & $2922$ & $0.5132$ & $3078$ & $16000$ & $10867$ & $5134$ & $0.6792$\\
$7000$ & $3647$ & $3354$ & $0.5210$ & $3646$ & $17000$ & $11855$ & $5146$ & $0.6974$\\
$8000$ & $4381$ & $3620$ & $0.5476$ & $4380$ & $18000$ & $12847$ & $5154$ & $0.7137$\\
$9000$ & $5228$ & $3773$ & $0.5809$ & $5227$ & $19000$ & $13842$ & $5159$ & $0.7285$\\
$10000$ & $5964$ & $4037$ & $0.5964$ & $5963$ & $20000$ & $14836$ & $5165$ & $0.7418$\\
\bottomrule
\end{tabular}
\end{table}

Among the $5165$ exponents $0\le a\le20000$ outside $\mathcal{A}$, $14$ have no candidate $K$ (the exponents $2^r+r-2$, $1\le r\le14$), $11$ are rejected by Algorithm~\ref{alg:membership} at its first iteration, and $5140$ at a later iteration. The script checks that the $11$ exponents rejected at the first iteration are exactly the $11$ exponents $a\le20000$ given by Theorem~\ref{thm:nonmembers}, all listed in Table~\ref{tab:families}: $6,24,90,348,1374,5472$ ($s=2$), $233,14575$ ($s=4$) and $7,107,1647$ ($s=3$). It also checks that the $14$ exponents $a\le20000$ in $\mathcal{A}$ decided without any iteration, $0,3,8,17,34,67,132,261,518,1031,2056,4105,8202,16395$, are exactly those of Theorem~\ref{thm:members}(1), and that the $11$ exponents $a\le20000$ in $\mathcal{A}$ decided after exactly one iteration, $2,12,28,46,176,416,690,971,2740,6564,10934$, are exactly those of Theorem~\ref{thm:members}(2). These three checks confirm Theorem~\ref{thm:firststep} for $a\le20000$.

Table~\ref{tab:iterations} gives the number of iterations of Algorithm~\ref{alg:membership} for the $19987$ exponents $0\le a\le20000$ that have a candidate $K$. Among them, $14751$ members and $5072$ non-members require at least $10$ iterations, that is $99.2\%$ of them, and the largest number of iterations is $19781$.

\begin{table}[H]
\centering
\caption{Number of iterations of Algorithm~\ref{alg:membership} for the exponents $0\le a\le20000$ with a candidate $K$; the last row counts the exponents with at least $10$ iterations.}
\label{tab:iterations}
\begin{tabular}{rrr@{\qquad}rrr}
\toprule
iterations & members & non-members & iterations & members & non-members\\
\midrule
$0$ & $14$ & $0$ & $5$ & $6$ & $8$\\
$1$ & $11$ & $11$ & $6$ & $8$ & $8$\\
$2$ & $7$ & $9$ & $7$ & $12$ & $9$\\
$3$ & $6$ & $4$ & $8$ & $7$ & $10$\\
$4$ & $9$ & $10$ & $9$ & $5$ & $10$\\
 & & & $\ge10$ & $14751$ & $5072$\\
\bottomrule
\end{tabular}
\end{table}

Table~\ref{tab:blocks} gives, for each $h\le14$, the number of candidates $K\in(2^{h-1},2^h]$, which is $2^{h-1}$, and the number of them for which $\beta(K)-3\in\mathcal{A}$. For $5\le h\le14$ the proportion takes values between $0.5000$, at $h=6$, and $0.8198$, at $h=14$.

\begin{table}[H]
\centering
\caption{Candidates $K\in(2^{h-1},2^h]$ and the number of them with $\beta(K)-3\in\mathcal{A}$.}
\label{tab:blocks}
\begin{tabular}{rrrr@{\qquad}rrrr}
\toprule
$h$ & candidates & members & proportion & $h$ & candidates & members & proportion\\
\midrule
$1$ & $1$ & $1$ & $1.0000$ & $8$ & $128$ & $103$ & $0.8047$\\
$2$ & $2$ & $2$ & $1.0000$ & $9$ & $256$ & $192$ & $0.7500$\\
$3$ & $4$ & $2$ & $0.5000$ & $10$ & $512$ & $277$ & $0.5410$\\
$4$ & $8$ & $8$ & $1.0000$ & $11$ & $1024$ & $744$ & $0.7266$\\
$5$ & $16$ & $10$ & $0.6250$ & $12$ & $2048$ & $1054$ & $0.5146$\\
$6$ & $32$ & $16$ & $0.5000$ & $13$ & $4096$ & $2087$ & $0.5095$\\
$7$ & $64$ & $45$ & $0.7031$ & $14$ & $8192$ & $6716$ & $0.8198$\\
\bottomrule
\end{tabular}
\end{table}

\subsection{The bounds of Theorem~\ref{thm:counting}}
\label{subsec:bounds-exp}
Table~\ref{tab:bounds} compares, for $H=\lfloor\log_2x\rfloor-1$, the number of exponents produced by the families in the proof of Theorem~\ref{thm:counting} with the explicit lower bound $2H-\log_2H-3$ for the members, and with $A(x)$ and $B(x)$ when $x\le20000$. For every $x$ of the table the family exponents are at most $x$, the member and non-member families are disjoint, the number of member exponents is at least $2H-\log_2H-3$, and for $x\le20000$ every member exponent is in $\mathcal{A}$ and every non-member exponent is not. For $x\le10000$ the families account for at most $21$ of the $A(x)$ members and $21$ of the $B(x)$ non-members.

\begin{table}[H]
\centering
\caption{Number of family exponents up to $x$ (members of Theorem~\ref{thm:members}, non-members of Theorems~\ref{thm:leading} and~\ref{thm:nonmembers}), the bound $2H-\log_2H-3$ of the proof of Theorem~\ref{thm:counting}, and the exact $A(x)$ and $B(x)$ for $x\le10000$.}
\label{tab:bounds}
\begin{tabular}{rrrrrrr}
\toprule
$x$ & $H$ & members (families) & $2H-\log_2H-3$ & $A(x)$ & non-members (families) & $B(x)$\\
\midrule
$16$ & $3$ & $4$ & $1.42$ & $12$ & $5$ & $5$\\
$64$ & $5$ & $8$ & $4.68$ & $38$ & $8$ & $27$\\
$256$ & $7$ & $11$ & $8.19$ & $182$ & $12$ & $75$\\
$1000$ & $8$ & $13$ & $10.00$ & $636$ & $14$ & $365$\\
$4096$ & $11$ & $19$ & $15.54$ & $2449$ & $20$ & $1648$\\
$10000$ & $12$ & $21$ & $17.42$ & $5964$ & $21$ & $4037$\\
$65536$ & $15$ & $26$ & $23.09$ & -- & $28$ & --\\
$10^{6}$ & $18$ & $33$ & $28.83$ & -- & $33$ & --\\
$10^{9}$ & $28$ & $52$ & $48.19$ & -- & $53$ & --\\
$10^{12}$ & $38$ & $73$ & $67.75$ & -- & $74$ & --\\
\bottomrule
\end{tabular}
\end{table}

\subsection{The successful states}
\label{subsec:states-exp}
The script computes the sets $S_J$ for all $J\le65536$, row by row, from Theorem~\ref{thm:step}: $w\in S_J$ if and only if $w=0$, or the iteration from $(J,w)$ does not fail and its result $(J-s,w')$ satisfies $w'\in S_{J-s}$. The values of $N(J)$ obtained in this way agree with Algorithm~\ref{alg:membership} for $J<200$ and for ten random $J$ in $[200,1500]$, and Algorithm~\ref{alg:membership} agrees with the big-integer greedy algorithm on all states with $J<120$. The symmetry of Proposition~\ref{prop:symmetry} holds for every $J\le65536$. The values of $N(J)$ printed by the script, for $J\le64$ and near each power of $2$ up to $2^{16}$, satisfy Proposition~\ref{prop:Npairs}. Table~\ref{tab:NJ} gives the extreme and mean values of $N(J)/J$ on the dyadic ranges. The integers $J\le65536$ with $N(J)=J$, that is with every state successful, are $1,2,4,12,16,17356,17360,17376,17632$.

\begin{table}[H]
\centering
\caption{The minimum, maximum and mean of $N(J)/J$ for $2^m\le J<2^{m+1}$, $0\le m\le15$, with the integers $J$ where the minimum and maximum are attained.}
\label{tab:NJ}
\begin{tabular}{rrrrrr}
\toprule
$m$ & $\min N(J)/J$ & at $J$ & $\max N(J)/J$ & at $J$ & mean $N(J)/J$\\
\midrule
$0$ & $1.0000$ & $1$ & $1.0000$ & $1$ & $1.0000$\\
$1$ & $0.6667$ & $3$ & $1.0000$ & $2$ & $0.8333$\\
$2$ & $0.5714$ & $7$ & $1.0000$ & $4$ & $0.7595$\\
$3$ & $0.4444$ & $9$ & $1.0000$ & $12$ & $0.7565$\\
$4$ & $0.5161$ & $31$ & $1.0000$ & $16$ & $0.7090$\\
$5$ & $0.4364$ & $55$ & $0.9412$ & $34$ & $0.6160$\\
$6$ & $0.4507$ & $71$ & $0.9355$ & $124$ & $0.7170$\\
$7$ & $0.5561$ & $187$ & $0.9846$ & $130$ & $0.8218$\\
$8$ & $0.5727$ & $447$ & $0.9927$ & $274$ & $0.7646$\\
$9$ & $0.2976$ & $699$ & $0.7489$ & $876$ & $0.5527$\\
$10$ & $0.3962$ & $2019$ & $0.9245$ & $1298$ & $0.7189$\\
$11$ & $0.2440$ & $2787$ & $0.7865$ & $3260$ & $0.5317$\\
$12$ & $0.1846$ & $5027$ & $0.8713$ & $8098$ & $0.5086$\\
$13$ & $0.5205$ & $9899$ & $0.9999$ & $15362$ & $0.8212$\\
$14$ & $0.8215$ & $26105$ & $1.0000$ & $17632$ & $0.9672$\\
$15$ & $0.7311$ & $39643$ & $0.9937$ & $51332$ & $0.8992$\\
\bottomrule
\end{tabular}
\end{table}

By Proposition~\ref{prop:Ncount}(2), the sets $S_J$ give the members of $\mathcal{A}$ with candidate $K\le65537$, hence $A(x)$ for $x\le65551=\beta(65537)-3$. The value $A(20000)=14836$ obtained in this way agrees with Section~\ref{subsec:counting-exp}. Table~\ref{tab:blocks16} gives, for $h\le16$, the proportion of members among the candidates $K\in(2^{h-1},2^h]$ and the mean of $N(K-1)/(K-1)$ over the same $K$; for $7\le h\le16$ the two numbers differ by at most $0.0171$. Table~\ref{tab:counting65} gives $A(x)$ for $x=25000,30000,\dots,65000$. For $x=1000,2000,\dots,65000$, the ratio $A(x)/x$ takes values between $0.5132$, at $x=6000$, and $0.8654$, at $x=62000$.

\begin{table}[H]
\centering
\caption{Members among the candidates $K\in(2^{h-1},2^h]$, and the mean of $N(J)/J$ over $J=K-1$ for the same $K$.}
\label{tab:blocks16}
\begin{tabular}{rrrrr@{\qquad}rrrrr}
\toprule
$h$ & candidates & members & proportion & mean $N/J$ & $h$ & candidates & members & proportion & mean $N/J$\\
\midrule
$1$ & $1$ & $1$ & $1.0000$ & $1.0000$ & $9$ & $256$ & $192$ & $0.7500$ & $0.7646$\\
$2$ & $2$ & $2$ & $1.0000$ & $0.8333$ & $10$ & $512$ & $277$ & $0.5410$ & $0.5527$\\
$3$ & $4$ & $2$ & $0.5000$ & $0.7595$ & $11$ & $1024$ & $744$ & $0.7266$ & $0.7189$\\
$4$ & $8$ & $8$ & $1.0000$ & $0.7565$ & $12$ & $2048$ & $1054$ & $0.5146$ & $0.5317$\\
$5$ & $16$ & $10$ & $0.6250$ & $0.7090$ & $13$ & $4096$ & $2087$ & $0.5095$ & $0.5086$\\
$6$ & $32$ & $16$ & $0.5000$ & $0.6160$ & $14$ & $8192$ & $6716$ & $0.8198$ & $0.8212$\\
$7$ & $64$ & $45$ & $0.7031$ & $0.7170$ & $15$ & $16384$ & $15878$ & $0.9691$ & $0.9672$\\
$8$ & $128$ & $103$ & $0.8047$ & $0.8218$ & $16$ & $32768$ & $29503$ & $0.9004$ & $0.8992$\\
\bottomrule
\end{tabular}
\end{table}

\begin{table}[H]
\centering
\caption{The counting function $A(x)$ for $25000\le x\le65000$, obtained from the sets $S_J$.}
\label{tab:counting65}
\begin{tabular}{rrr@{\qquad}rrr}
\toprule
$x$ & $A(x)$ & $A(x)/x$ & $x$ & $A(x)$ & $A(x)/x$\\
\midrule
$25000$ & $19692$ & $0.7877$ & $50000$ & $42335$ & $0.8467$\\
$30000$ & $24433$ & $0.8144$ & $55000$ & $47180$ & $0.8578$\\
$35000$ & $29021$ & $0.8292$ & $60000$ & $51819$ & $0.8637$\\
$40000$ & $33160$ & $0.8290$ & $65000$ & $56153$ & $0.8639$\\
$45000$ & $37737$ & $0.8386$ & & &\\
\bottomrule
\end{tabular}
\end{table}

\subsection{The forest of states}
\label{subsec:forest-exp}
The script checks Theorem~\ref{thm:forest} as follows. The number $F(J)$ of failing states obtained from the rows equals the number given by part (1) for every $J\le65536$, and the largest value of $F(J)$ in this range is $3$. The sum $\sum_{J\le L}F(J)$ equals $\sum_{\sigma=2}^{L}\lfloor(L+1-\sigma)/2^{\sigma-1}\rfloor$ for $L=10,100,1000,10000,65536$, with the values $6,94,991,9991,65519$. Every state $(J',w')$ with $J'\le600$ has exactly $v_2(J'+1+w')$ preimages under $\Phi$, counted by applying $\Phi$ to all states of levels up to $613$, and the recursion of part (3) for $N(J)$ holds for $J\le1200$.

The script labels every state by the root of its tree and counts, at the levels $J=2^m$, $5\le m\le16$, the number of distinct trees among the $J$ states of the level and the shares of the largest trees (Table~\ref{tab:trees}). At each of these levels the largest tree is the tree of the root $(1,0)$, and its share equals $N(J)/(2J)$, as stated by Proposition~\ref{prop:roots}. At the level $J=65536$, the ten largest trees are those of the roots $(1,0)$, $(47321,0)$, $(51081,0)$, $(47257,0)$ and $(9631,0)$, with $29090$, $16376$, $6838$, $2810$ and $1962$ states, and those of the failing states of the levels $61364$ ($s=5$), $61361$ ($s=2$), $52582$ ($s=3$), $52581$ ($s=2$) and $56327$ ($s=8$), with $1614$, $1614$, $1578$, $1578$ and $386$ states.

\begin{table}[H]
\centering
\caption{The trees of the forest at the levels $J=2^m$: the number of distinct trees among the $J$ states of the level, the proportion $N(J)/J$ of successful states, and the shares of the largest tree, which is the tree of $(1,0)$ at every level, and of the $5$ and $10$ largest trees.}
\label{tab:trees}
\begin{tabular}{rrrrrr}
\toprule
$J$ & trees & $N(J)/J$ & tree of $(1,0)$ & $5$ largest & $10$ largest\\
\midrule
$32$ & $8$ & $0.6250$ & $0.3125$ & $0.8750$ & $1.0000$\\
$64$ & $12$ & $0.5625$ & $0.2812$ & $0.7188$ & $0.9688$\\
$128$ & $9$ & $0.9375$ & $0.4688$ & $0.9531$ & $1.0000$\\
$256$ & $15$ & $0.8438$ & $0.4219$ & $0.8047$ & $0.9531$\\
$512$ & $17$ & $0.7422$ & $0.3711$ & $0.7188$ & $0.9102$\\
$1024$ & $20$ & $0.5469$ & $0.2734$ & $0.7422$ & $0.9355$\\
$2048$ & $21$ & $0.5293$ & $0.2646$ & $0.7783$ & $0.9521$\\
$4096$ & $25$ & $0.4668$ & $0.2334$ & $0.6982$ & $0.8931$\\
$8192$ & $22$ & $0.8335$ & $0.4167$ & $0.7751$ & $0.9609$\\
$16384$ & $17$ & $0.9868$ & $0.4934$ & $0.9744$ & $0.9945$\\
$32768$ & $19$ & $0.9535$ & $0.4767$ & $0.9462$ & $0.9908$\\
$65536$ & $27$ & $0.8878$ & $0.4439$ & $0.8709$ & $0.9742$\\
\bottomrule
\end{tabular}
\end{table}

\subsection{The bottom-up recursion}
\label{subsec:bottomup-exp}
The script computes $S_J$ for $J\le131072$ with Theorem~\ref{thm:bottomup}, in $27.5$ seconds. The sets obtained coincide with those of Section~\ref{subsec:states-exp} for every $J\le3000$; the values of $N(J)$ coincide for $J\le65536$, and so does the membership of every initial state with $K\le65537$. For every $J\le131072$, $S_J$ is symmetric, $S_J$ has period $J/2$ when $J$ is even, $N(2k+1)=N(2k)$, and $4\mid N(J)$ when $J\ge4$. For the block $h=17$, the proportion of members among the $65536$ candidates is $56692/65536=0.8651$, and the mean of $N(K-1)/(K-1)$ over the block is $0.8652$. On the range $2^{16}\le J<2^{17}$, $N(J)/J$ takes values between $0.6683$, at $J=70695$, and $0.9996$, at $J=95306$, with mean $0.8652$. Table~\ref{tab:counting131} gives $A(x)$ for $70000\le x\le130000$; the value $A(65000)=56153$ coincides with Table~\ref{tab:counting65}. For $x=1000,2000,\dots,131000$, the ratio $A(x)/x$ takes values between $0.5132$, at $x=6000$, and $0.8750$, at $x=109000$.

\begin{table}[H]
\centering
\caption{The counting function $A(x)$ for $70000\le x\le130000$, obtained from the recursion of Theorem~\ref{thm:bottomup}.}
\label{tab:counting131}
\begin{tabular}{rrr@{\qquad}rrr}
\toprule
$x$ & $A(x)$ & $A(x)/x$ & $x$ & $A(x)$ & $A(x)/x$\\
\midrule
$70000$ & $60188$ & $0.8598$ & $105000$ & $91604$ & $0.8724$\\
$75000$ & $63912$ & $0.8522$ & $110000$ & $96233$ & $0.8748$\\
$80000$ & $68038$ & $0.8505$ & $115000$ & $100429$ & $0.8733$\\
$85000$ & $72221$ & $0.8497$ & $120000$ & $104238$ & $0.8687$\\
$90000$ & $76886$ & $0.8543$ & $125000$ & $108240$ & $0.8659$\\
$95000$ & $81814$ & $0.8612$ & $130000$ & $112452$ & $0.8650$\\
$100000$ & $86767$ & $0.8677$ & & &\\
\bottomrule
\end{tabular}
\end{table}

\subsection{The families of Theorem~\ref{thm:symfamilies}}
\label{subsec:symfam-exp}
The formula $c(2^{2^r}-1)=2^{2^r+r-1}$ holds for $0\le r\le12$. For $h\le300$, Theorem~\ref{thm:symfamilies}(2) gives $282$ pairs $(i,h)$ and Theorem~\ref{thm:symfamilies}(3) gives $222$ pairs $(i,h)$; for all of them $w$ is an even positive integer and $2^{h-1}+1<K<2^h$. Every exponent of parts (1) and (2) at most $131088=\beta(131073)-3$ is in $\mathcal{A}$, every exponent of part (3) in this range is not, according to the sets $S_J$ of Section~\ref{subsec:bottomup-exp}, and the big-integer greedy algorithm agrees for $a\le4000$. Table~\ref{tab:symfam} lists the exponents of parts (2) and (3) with $h\le17$.

\begin{table}[H]
\centering
\caption{The exponents $a=K+h-3$ of Theorem~\ref{thm:symfamilies}(2) (members) and~(3) (non-members) with $h\le17$, with $\sigma=2^{i-1}+1$.}
\label{tab:symfam}
\begin{tabular}{rrrrr@{\qquad}rrrrr}
\toprule
\multicolumn{5}{c}{Members, part (2)} & \multicolumn{5}{c}{Non-members, part (3)}\\
$i$ & $\sigma$ & $h$ & $K$ & $a$ & $i$ & $\sigma$ & $h$ & $K$ & $a$\\
\midrule
$1$ & $2$ & $4$ & $10$ & $11$ & $2$ & $3$ & $5$ & $19$ & $21$\\
$2$ & $3$ & $6$ & $35$ & $38$ & $2$ & $3$ & $8$ & $147$ & $152$\\
$1$ & $2$ & $7$ & $74$ & $78$ & $3$ & $5$ & $8$ & $133$ & $138$\\
$3$ & $5$ & $9$ & $261$ & $267$ & $2$ & $3$ & $11$ & $1171$ & $1179$\\
$1$ & $2$ & $10$ & $586$ & $593$ & $3$ & $5$ & $13$ & $4229$ & $4239$\\
$2$ & $3$ & $10$ & $547$ & $554$ & $4$ & $9$ & $13$ & $4105$ & $4115$\\
$1$ & $2$ & $13$ & $4682$ & $4692$ & $2$ & $3$ & $14$ & $9363$ & $9374$\\
$2$ & $3$ & $14$ & $8739$ & $8750$ & $2$ & $3$ & $17$ & $74899$ & $74913$\\
$4$ & $9$ & $14$ & $8201$ & $8212$ & & & & &\\
$3$ & $5$ & $15$ & $16645$ & $16657$ & & & & &\\
$1$ & $2$ & $16$ & $37450$ & $37463$ & & & & &\\
\bottomrule
\end{tabular}
\end{table}

Table~\ref{tab:allfam} gives the number of exponents up to $x$ produced by all the families of Theorems~\ref{thm:leading}, \ref{thm:members}, \ref{thm:nonmembers} and~\ref{thm:symfamilies}, with $H=\lfloor\log_2x\rfloor-1$, together with $(3+C_1)H$, $(\frac54+\frac E2+C_2)H$ and, for $x\le100000$, the exact values of $A(x)$ and $B(x)$. For every $x$ of the table, the member and non-member exponents are at most $x$ and disjoint, and for $x\le100000$ every member exponent is in $\mathcal{A}$ and every non-member exponent is not.

\begin{table}[H]
\centering
\caption{Exponents up to $x$ produced by all the explicit families, compared with $(3+C_1)H$ and $(\frac54+\frac E2+C_2)H$ of Theorem~\ref{thm:counting2}, and with $A(x)$ and $B(x)$.}
\label{tab:allfam}
\begin{tabular}{rrrrrrrr}
\toprule
$x$ & $H$ & members & $(3+C_1)H$ & $A(x)$ & non-members & $(\frac54+\frac E2+C_2)H$ & $B(x)$\\
\midrule
$10^3$ & $8$ & $22$ & $31.72$ & $636$ & $17$ & $22.54$ & $365$\\
$10^4$ & $12$ & $37$ & $47.59$ & $5964$ & $25$ & $33.81$ & $4037$\\
$10^5$ & $15$ & $49$ & $59.48$ & $86767$ & $35$ & $42.27$ & $13234$\\
$10^6$ & $18$ & $61$ & $71.38$ & -- & $42$ & $50.72$ & --\\
$10^9$ & $28$ & $100$ & $111.04$ & -- & $69$ & $78.90$ & --\\
$10^{12}$ & $38$ & $139$ & $150.69$ & -- & $97$ & $107.08$ & --\\
\bottomrule
\end{tabular}
\end{table}

\subsection{Odd primes}
\label{subsec:primes-exp}
For $p=3,5,7,11$ the script checks Lemma~\ref{lem:cp}(3) for $n\le50000$ and Lemma~\ref{lem:cp}(1) for $pn\le200000$ against the definition of $c_p$, and Proposition~\ref{prop:Fp} for $n\le30$ by computing the product $(1-X)\cdots(1-X^n)$ in $\mathbb{F}_p[X]$ and dividing it by $1-X$ as long as possible. A brute-force search over $n\le200000$ decides the membership of the exponents $a\le13,8,7,5$ for $p=3,5,7,11$; the members found are $0,3,4,6,7,8,9,10,13$ for $p=3$ (with $c_3(n)=3^a$ for $n=1,13,27,215,513,1457,3645,9841,196829$), $0,5,6,8$ for $p=5$, $0,7$ for $p=7$ and $0$ for $p=11$. In these ranges the recursion of Theorem~\ref{thm:primestep} and the greedy algorithm applied to the big integers $p^{a+1}$ and $t_i$ agree with the search, and they agree with each other for $a\le1200$. The exponents $a\le20000$ without candidate are exactly those of Theorem~\ref{thm:primes}(3): $1,5,15,43,125,369,1099,3287,9849$ for $p=3$, $1,7,33,159,785,3911,19537$ for $p=5$, $1,9,59,403,2805,19613$ for $p=7$ and $1,13,135,1467,16109$ for $p=11$. The three parts of Theorem~\ref{thm:primefamilies} are confirmed; part (3) gives the exponents $2,22,186,1646,14770,132870$ for $p=3$, $3,80,1957$ for $p=5$, $4,202,9808$ for $p=7$ and $6,734,88582$ for $p=11$. Table~\ref{tab:primes} gives $A_p(x)$ for $x\le3000$ and the outcomes of the recursion for $a\le3000$.

\begin{table}[H]
\centering
\caption{The counting functions $A_p(x)$ for $p=3,5,7,11$, and the outcomes of the recursion of Theorem~\ref{thm:primestep} for $0\le a\le3000$: no candidate, immediate failure, a digit $d>p-1$, a remainder $w'>(p-1)i$, and success.}
\label{tab:primes}
\begin{tabular}{rrrrr}
\toprule
 & $p=3$ & $p=5$ & $p=7$ & $p=11$\\
\midrule
$A_p(500)$ & $381$ & $239$ & $212$ & $215$\\
$A_p(1000)$ & $733$ & $397$ & $556$ & $397$\\
$A_p(1500)$ & $1105$ & $616$ & $896$ & $577$\\
$A_p(2000)$ & $1442$ & $882$ & $1173$ & $804$\\
$A_p(2500)$ & $1893$ & $1252$ & $1485$ & $1100$\\
$A_p(3000)$ & $2317$ & $1676$ & $1812$ & $1334$\\
$A_p(3000)/3000$ & $0.7723$ & $0.5587$ & $0.6040$ & $0.4447$\\
\midrule
no candidate & $7$ & $5$ & $5$ & $4$\\
immediate failure & $4$ & $7$ & $6$ & $10$\\
digit $d>p-1$ & $343$ & $197$ & $222$ & $125$\\
remainder $w'>(p-1)i$ & $330$ & $1116$ & $956$ & $1528$\\
success & $2317$ & $1676$ & $1812$ & $1334$\\
\bottomrule
\end{tabular}
\end{table}

For $p=3$ the $4$ immediate failures up to $3000$ are the exponents $2,22,186,1646$ of Theorem~\ref{thm:primefamilies}(3), as Theorem~\ref{thm:immediate} states. Grouping the candidates by $g$, the proportion of members is $0.6667,0.7778,0.7037,0.8395,0.6626,0.7586$ for $g=2,\dots,7$ when $p=3$; $0.4000,0.6400,0.5200,0.3952$ for $g=2,\dots,5$ when $p=5$; $0.2857,0.6735,0.4052,0.6318$ for $g=2,\dots,5$ when $p=7$; and $0.1818,0.6198,0.3681$ for $g=2,3,4$ when $p=11$.

\subsection{Immediate failures and the bottom-up recursion for odd primes}
\label{subsec:primes2-exp}
For $a\le100000$, the script determines the immediate failures from the first step of Theorem~\ref{thm:primestep} and compares them with the exponents given by the triples $(g,e,j)$ of Theorem~\ref{thm:immediate}. For $p=2$ there is none. For $p=3,5,7,11$ the two sets coincide; they are listed in Table~\ref{tab:immediate}. For $p=3$ they are the exponents of Theorem~\ref{thm:primefamilies}(3), and for every $p$ and $g$ their number is at most $(p-1)(p-2)$; the largest number for a single $g$ is $1,3,4,6$ for $p=3,5,7,11$.

\begin{table}[H]
\centering
\caption{The immediate failures $a\le100000$ (Theorem~\ref{thm:immediate}).}
\label{tab:immediate}
\begin{tabular}{rl}
\toprule
$p$ & immediate failures $a\le100000$\\
\midrule
$2$ & none\\
$3$ & $2,22,186,1646,14770$\\
$5$ & $2,3,41,54,80,1306,1957,24420,32558,48834$\\
$7$ & $2,4,20,82,102,202,3272,4906,6540,9808$\\
$11$ & $2,3,4,6,20,185,246,368,490,734,3224,19688,25312,29530,44293,59056,88582$\\
\bottomrule
\end{tabular}
\end{table}

The script computes the sets $S^{(p)}_K$ for $K\le10000$ with Theorem~\ref{thm:primebottomup}, in less than $3$ seconds for each prime. For every $K\le10000$ and $p=3,5,7,11$, $S^{(p)}_K$ is symmetric under $w\mapsto(p-1)K-w$, $N_p(K+1)=N_p(K)$ when $p\nmid K$, and $N_p(K+1)=p\,\#\{w\in S^{(p)}_K:\ p\mid w\}$ when $p\mid K$; the members obtained from these sets coincide with those of Theorem~\ref{thm:primestep} for $a\le1500$. Table~\ref{tab:primes10000} gives $A_p(x)$ for $x\le10000$. Table~\ref{tab:primegroups} groups the candidates $K$ by $g=g(K)$ and compares the proportion of members with the mean of $N_p(K)/((p-1)K+1)$, the proportion of successful states, over the same $K$. For every complete group with at least $2000$ candidates, namely $g=8,9$ for $p=3$, $g=6$ for $p=5$ and $g=5$ for $p=7$, the two numbers differ by at most $0.0110$.

\begin{table}[H]
\centering
\caption{The counting functions $A_p(x)$ for $x\le10000$, obtained from Theorem~\ref{thm:primebottomup}.}
\label{tab:primes10000}
\begin{tabular}{rrrrrrrr}
\toprule
$x$ & $A_3(x)$ & $A_5(x)$ & $A_7(x)$ & $A_{11}(x)$ & $A_3(x)/x$ & $A_5(x)/x$ & $A_7(x)/x$\\
\midrule
$2000$ & $1442$ & $882$ & $1173$ & $804$ & $0.7210$ & $0.4410$ & $0.5865$\\
$4000$ & $3082$ & $2413$ & $2348$ & $1718$ & $0.7705$ & $0.6032$ & $0.5870$\\
$6000$ & $4664$ & $3611$ & $3406$ & $2677$ & $0.7773$ & $0.6018$ & $0.5677$\\
$8000$ & $5684$ & $4866$ & $4764$ & $3576$ & $0.7105$ & $0.6082$ & $0.5955$\\
$10000$ & $6518$ & $6097$ & $6244$ & $4433$ & $0.6518$ & $0.6097$ & $0.6244$\\
\bottomrule
\end{tabular}
\end{table}

\begin{table}[H]
\centering
\caption{Candidates $K$ grouped by $g=g(K)$: number of candidates, proportion of members, and mean of $N_p(K)/((p-1)K+1)$ over the group (complete groups only).}
\label{tab:primegroups}
\begin{tabular}{rrrrr@{\qquad}rrrrr}
\toprule
$p$ & $g$ & candidates & members & mean density & $p$ & $g$ & candidates & members & mean density\\
\midrule
$3$ & $5$ & $81$ & $0.8395$ & $0.7932$ & $5$ & $4$ & $125$ & $0.5200$ & $0.5304$\\
$3$ & $6$ & $243$ & $0.6626$ & $0.6559$ & $5$ & $5$ & $625$ & $0.3952$ & $0.4173$\\
$3$ & $7$ & $729$ & $0.7586$ & $0.7565$ & $5$ & $6$ & $3125$ & $0.6474$ & $0.6513$\\
$3$ & $8$ & $2187$ & $0.7796$ & $0.7686$ & $7$ & $4$ & $343$ & $0.4052$ & $0.4243$\\
$3$ & $9$ & $6561$ & $0.6033$ & $0.6005$ & $7$ & $5$ & $2401$ & $0.6318$ & $0.6319$\\
 & & & & & $11$ & $4$ & $1331$ & $0.3681$ & $0.3926$\\
\bottomrule
\end{tabular}
\end{table}

For $x=1000,2000,\dots,10000$, the ratio $A_p(x)/x$ takes values between $0.6518$ and $0.7773$ for $p=3$, between $0.3970$ and $0.6132$ for $p=5$, between $0.5560$ and $0.6244$ for $p=7$, and between $0.3970$ and $0.4486$ for $p=11$.

\section{Conclusion}
\label{sec:conclusion}
The identity $c(n)=n+\frac12\sum_{i\in\mathcal{B}(n)}i2^i$ turns the question of Nicolas into the question of which powers of $2$ are sums of distinct terms of the superincreasing sequence $(j2^j)_{j\ge1}$ (Theorem~\ref{thm:equiv}). For every exponent there is at most one possible leading term, and the exponents without one are exactly $2^r+r-2$ (Theorem~\ref{thm:leading}); the remaining exponents are decided by a recursion on pairs of integers bounded by $a+3$ (Theorem~\ref{thm:step}, Corollary~\ref{cor:algo}). The closed formula $c(2^{K-2}+2^{K-s-2})=2^{K+h-3}$ and the failure criterion of Theorem~\ref{thm:step} give infinite explicit families of members and of non-members, which contain the families of Nicolas as the cases $s=1$ and $s=2$ (Theorems~\ref{thm:members} and~\ref{thm:nonmembers}) and are exactly the exponents decided by at most one iteration of the recursion (Theorem~\ref{thm:firststep}), and they give the bounds $A(x)\ge(2+o(1))\log_2x$ and $B(x)\ge(2.0533\ldots+o(1))\log_2x$ (Theorem~\ref{thm:counting}). The experiments of Section~\ref{sec:experiments} confirm these statements by three independent methods, reproduce the table of Nicolas, whose values are the numbers $A(x)-1$ of exponents $1\le a\le x$ in $\mathcal{A}$, and give $A(x)$ for $x\le65000$, with $A(x)/x$ between $0.5132$ and $0.8654$ for $x=1000,2000,\dots,65000$. The successful states satisfy the symmetry $w\mapsto J-1-w$, $N(2k+1)=N(2k)$ and $4\mid N(J)$ (Propositions~\ref{prop:symmetry} and~\ref{prop:Npairs}), and for $7\le h\le16$ the proportion of members among the candidates $K\in(2^{h-1},2^h]$ differs from the mean of $N(K-1)/(K-1)$ by at most $0.0171$. The states form a forest whose roots are the states $(J,0)$ and the failing states, with $v_2(J'+1+w')$ children at each state $(J',w')$ (Theorem~\ref{thm:forest}); exactly half of the successful states of each level lie in the tree of $(1,0)$ (Proposition~\ref{prop:roots}), and at the levels $2^m\le65536$ the ten largest trees contain between $89.31\%$ and $100\%$ of the states of the level. The sets $S_J$ also satisfy a recursion from the smallest elements of $T$ upwards, with period $J/2$ for even $J$ (Theorem~\ref{thm:bottomup}); with this recursion $A(x)$ is computed for $x\le131000$, and $A(x)/x$ lies between $0.5132$ and $0.8750$ for $x=1000,2000,\dots,131000$. The symmetry gives further explicit families and the bounds $A(x)\ge(3.9655\ldots+o(1))\log_2x$ and $B(x)\ge(2.8178\ldots+o(1))\log_2x$ (Theorems~\ref{thm:symfamilies} and~\ref{thm:counting2}). For every prime $p$, the function $c_p(n)=\sum_{k\le n}p^{v_p(k)}$, which counts the factor $1-X$ in $(1-X)\cdots(1-X^n)$ over $\mathbb{F}_p[X]$, admits the same reduction, a unique candidate and a recursion, and for odd $p$ there are infinitely many members and non-members (Theorems~\ref{thm:primes}, \ref{thm:primestep} and~\ref{thm:primefamilies}); the immediate failures, which do not occur for $p=2$, are described completely, and the bottom-up recursion and the symmetry extend to every prime (Theorems~\ref{thm:immediate} and~\ref{thm:primebottomup}). The asymptotic behaviour of $A(x)$ asked for in~\cite{nicolas2005open} is not determined by these results.

\subsection*{Declaration of interests}

The author declares no competing interests.

\subsection*{Funding sources}

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

\subsection*{Declaration of generative AI in scientific writing}

The author used Claude Opus 5.5 to assist in deriving the proofs, to write the experiment script \texttt{powers\_of\_two\_c.py}, and in preparing this manuscript; the author ran the experiments. After using this tool, the author reviewed and edited the content as needed and takes full responsibility for the content of the publication.

\subsection*{Data availability}

The experiments of Section~\ref{sec:experiments} are reproduced by running the script \texttt{powers\_of\_two\_c.py} with the options \texttt{--xmax 20000 --jmax2 131072 --pxmax 3000 --primes 3,5,7,11 --kmax 10000}, using Python~3.12.3 and NumPy~2.4.6.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{elsarticle-num}
\bibliography{biblio}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}