<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\definecolor{red}{rgb}{1,0,0}

\usepackage{color}




\usepackage[figuresright]{rotating} 

\usepackage{algorithmic}
\usepackage{algorithm}

\def\mod{ \mathop{ \rm mod} \nolimits}

\newdimen\localwidth

\let\eps=\varepsilon
\let\phi=\varphi
\let\Dst=\displaystyle
\def\3{\ss{}}
\def\dd{\delta}
\def\dist{{\rm dist}}
\def\id{{\rm id}}
\def\Mu{{\rm M}}
\def\deg{\mathop{\rm deg}}
\def\ST{\widehat{S}}
\def\Psihat{\widehat{\Psi}}
\def\Phihat{\widehat{\Phi}}
\def\cupdot{\dot{\cup}}
\def\veedot{\dot{\vee}}
\def\diam{\mathop{\rm diam}}
\def\LHS{\mathop{\rm LHS}}
\def\RHS{\mathop{\rm RHS}}

\newcommand{\triangleup}{\mathrel{\reflectbox{\rotatebox[origin=c]{270}{\small$\triangleleft\hspace{0.63mm}$}}}}


\makeatletter
\newdimen\@tempx
\newbox\@tempbox
\makeatother

\begin{document}

\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Precious Metal Sequences and \\
\vskip .1in
Sierpi\'{n}ski-Type Graphs 
}
\vskip 1cm
Andreas M. Hinz\footnote{Corresponding author.}\\
Department of Mathematics\\
Ludwig-Maximilians-Universit\"{a}t M\"{u}nchen\\
Theresienstra\3e 39\\
80333 Munich\\
Germany \\
\href{mailto:hinz@math.lmu.de}{\tt hinz@math.lmu.de}\\
\ \\
Paul K. Stockmeyer \\
Department of Computer Science \\
The College of William \&amp; Mary\\
P.O.~Box 8795 \\
Williamsburg, VA 23187-8795\\
USA \\
\href{mailto:pkstockmeyer@cox.net}{\tt pkstockmeyer@cox.net} 
\end{center}

\vskip .2 in



\begin{abstract}
 Sierpi\'{n}ski graphs $S_p^n$ and Sierpi\'{n}ski triangle graphs $\ST_p^n$ form two-parametric families of connected simple graphs which are related, for $p=3$, to the Tower of Hanoi with $n$ discs and for $n\rightarrow \infty$ to the Sierpi\'{n}ski triangle fractal. The vertices of minimal degree play a special role as extreme vertices in $S_p^n$ and primitive vertices in $\ST_p^n$. The key concept of this note is that of an $m$-key vertex whose distance to one of the extreme or primitive vertices, respectively, is $m$ times the distance to another one. The number of such vertices and the distances occurring lead to integer sequences with respect to parameter $n$ like, e.g., the Fibonacci sequence (golden) for $p=3$ and the Pell sequence (silver) for $p=4$. The elements of most of these sequences form self-generating sets. We discuss the cases $m=1,2,3,4$ in detail.
\end{abstract}



\section{Introduction}\label{sec:intro}


The vertices of {\em Sierpi\'{n}ski graph} $S_p^n$ with {\em base} $p\in\mathbb{N}$, $p\geq 2$, and {\em exponent} $n\in\mathbb{N}_0$ are $n$-tuples of the set $P:=[p]_0:=\{0,\ldots,p-1\}$ and written as $s=s_n\ldots s_1$ with $s_d\in P$ for $d\in [n]:=\{1,\ldots,n\}$. The edge set is given by
\begin{equation}\label{eqn:defedge}
E(S_p^n)=\left\{\{\underline{s}ij^{d-1},\underline{s}ji^{d-1}\}\ |\ \{i,j\}\in \textstyle{{P\choose 2}},\;d\in [n],\;\underline{s}=s_n\ldots s_{d+1}\in P^{n-d}\right\}.
\end{equation}
Note that $S_p^0=\left(\{\epsilon\},\emptyset\right)\cong K_1$ with the {\em empty word} ${\epsilon}$, $S_p^1\cong K_p$ and that $S_2^n$ is a path on $2^n$ vertices. Sierpi\'{n}ski graphs were introduced in the 1990s as mathematical models for the famous {\em Tower of Hanoi} ($p=3$) and the {\em Chinese Rings} ($p=2$); see \cite[Chapter~4]{hinz-2013}. In the past two decades they developed a life on their own as can be seen in a recent survey \cite{hinz-2016}. Apart from many graph parameters determined, metric properties have been investigated, and the graphs $S_3^n$ were used to approximate the fractal structure of the {\em Sierpi\'{n}ski triangle} (see \cite{hinz-1990}).

If we concatenate $s_{n+1}=k\in P$ to the left of all vertices of $S_p^n$ we get what we may call the graph $kS_p^n\cong S_p^n$ as a subgraph of $S_p^{1+n}$. These $p$ copies of $S_p^n$ are mutually linked in $S_p^{1+n}$ by the so-called {\em critical edges} $\{ij^n,ji^n\}$, $\{i,j\}\in {P\choose 2}$, according to \eqref{eqn:defedge}. This shows that Sierpi\'{n}ski graphs $S_p^n$ are connected and therefore endowed with the canonical distance function $\dd$ where $\dd(s,t)$ is the length of a shortest $s,t$-path in $S_p^n$. The importance of the critical edges lies in the fact that for $p\geq 3$ a shortest $i\overline{s},j\overline{t}$-path may either run through critical edge $\{ij^n,ji^n\}$ ({\em direct path}) or via two critical edges, namely $\{ik^n,ki^n\}$ and $\{kj^n,jk^n\}$ for some (but only one) $k\in P\setminus \{i,j\}$ ({\em indirect path}). The decision whether the direct or an indirect path is shortest (or both are) and for which $k$, is not easy and has been analyzed and solved with an algorithm by Hinz and Holz auf der Heide \cite{hinz-2014}. The decisive ingredient is the distance $\dd(s,j^n)$ of an arbitrary vertex $s\in P^n$ to a so-called {\em extreme vertex} $j^n$ in $S_p^n$. It is given (see \cite[Theorem~4.5]{hinz-2013}) by the formula
\begin{equation}\label{eqn:distextreme}
\forall\,s\in P^n\;\forall\,j\in P:\dd(s,j^n)=\sum_{d=1}^n (s_d\neq j)\cdot 2^{d-1},
\end{equation}
where we make use of the {\em Iverson bracket} (or {\em Iverson convention}) which assigns a numerical (binary) value 
$(\mathcal{A})$ to a statement $\mathcal{A}$; it is defined by
$(\mathcal{A}) =1$, if $\mathcal{A}$ is true, and $(\mathcal{A}) =0$, if $\mathcal{A}$ is false. 
Obviously, $\dd(s,j^n)\leq 2^n-1$ and putting $s=i^n$ for some $i\in P\setminus\{j\}$ we have $\diam(S_p^n)=\dd(i^n,j^n)=2^n-1$.
Another immediate consequence of \eqref{eqn:distextreme} is 
the following invariant:
\begin{equation}\label{eqn:invariant}
\forall\,s\in P^n:\sum_{j=0}^{p-1} \dd(s,j^n)=(p-1)\cdot (2^n-1).
\end{equation}



Sierpi\'{n}ski graphs $S_3^n$ are isomorphic to {\em Hanoi graphs} $H_3^n$; see \cite[pp.~177ff]{hinz-2013}. For these, the number of {\em 2-key vertices} with $\dd(s,2^n)=2\cdot \dd(s,0^n)$ has been found to be Fibonacci number $F_{n-1}$ in \cite[Theorem~3.1]{hinz-2019}. Here, for $n\geq 3$, the {\em 2-key distances} $\dd(s,0^n)$ have the form $2\beta +2^{n-2}+1$ with $\beta$ running through the set of $(n-3)$-bit numbers without consecutive $0$s; see \cite[Lemma~3.2]{hinz-2019}. The fact that all 2-key distances are odd follows also from the observation from \eqref{eqn:distextreme} that exactly one of the distances $\dd(s,j^n)$ is even, namely for $j=s_1$ in $S_3^n$ and for $j=s_n\triangleup\cdots\triangleup s_1$ in $H_3^n$, where the operation given by $i\triangleup k=i+(3-2i-k)(i\neq k)$ for $i,k\in \{0,1,2\}$ has to be evaluated from the right; see \cite[(2.8)]{hinz-2013}.

In the present note we want to extend these results in three ways. We will consider Sierpi\'{n}ski graphs of any base $p\geq 2$ (Section~\ref{sec:sierpinski}), thereby looking at {\em m-key vertices}, i.e., those $s\in P^n$ for which $\dd(s,(p-1)^n)=m\cdot \dd(s,0^n)$ and their respective {\em m-key distances} for $m=1$ (Section~\ref{sec:Sm1}), $m=2$
(Section~\ref{sec:Sm2}), $m=3$ (Section~\ref{sec:Sm3}), and $m=4$ (Section~\ref{sec:Sm4}). Finally, we will consider the corresponding questions for {\em Sierpi\'{n}ski triangle graphs} $\ST_p^n$ (Section~3). These are graphs which have often been mistaken for Sierpi\'{n}ski graphs and even been called so (see \cite{hinz-2016} for a discussion), but whose metric properties are somewhat more difficult to access (see \cite{hinz-2020}). Our focus will be on integer sequences emerging from these considerations. Some of the sequences come from the so-called {\em self-generating sets}, like, e.g., the {\em Mersenne sequence} $M_n=2^n-1$ (\seqnum{A000225}, referring  to the {\it On-Line Encyclopedia of Integer Sequences} (OEIS)) with $\alpha=1$ and $\mathcal{F}=\{k\mapsto 2k+1\}$ in the following lemma.

\begin{lemma}\label{lem:selfgen}
Let $\alpha\in\mathbb{N}$ and $\mathcal{F}$ be a finite set of functions from $\mathbb{N}$ to $\mathbb{N}$ with
\begin{equation}\label{eqn:increasing}
\forall\,f\in \mathcal{F}\;\forall\,x\in\mathbb{N}:f(x)&gt;x.
\end{equation} 
We say that $\Gamma\subset\mathbb{N}$ fulfills property ${\rm SG}(\alpha,\mathcal{F})$, iff $\{\alpha\}\cup\,\bigcup\{f(\Gamma)\ |\ f\in \mathcal{F}\}\subset \Gamma$. \\
Then the following are equivalent:

{\em 1}. $\mathbb{N}\supset C=\{\alpha\}\cup\,\bigcup\{f(C)\ |\ f\in \mathcal{F}\}$,

{\em 2}. $C=\{c_k\circ \cdots\circ c_1(\alpha)\ |\ c_\ell\in \mathcal{F},\;\ell\in [k],\;k\in\mathbb{N}_0\}$,

{\em 3}. $C=\bigcap\{\Gamma\subset\mathbb{N}\ |\ \Gamma\;{\rm fulfills}\;{\rm SG}(\alpha,\mathcal{F})\}$,

{\em 4}. $C$ is the smallest subset of $\mathbb{N}$ (w.r.t.~``$\subset$'') that fulfills ${\rm SG}(\alpha,\mathcal{F})$.

\noindent Such a $C$ is called a {\em self-generating set}, $\alpha$ is its {\em seed} and $\mathcal{F}$ is its {\em generating function set}. Points~{\em 2} to {\em 4} guarantee that $C$ is defined uniquely by~{\em 1}.
\end{lemma}

\begin{proof}
{1}.~$\Rightarrow$ {2}. Let $\mathbb{N}\supset C=\{\alpha\}\cup\,\bigcup\{f(C)\ |\ f\in \mathcal{F}\}$ and define $C':=\bigcup\{C_k\ |\ k\in\mathbb{N}_0\}$ with $C_k:=
\{c_k\circ \cdots\circ c_1(\alpha)\ |\ c_\ell\in \mathcal{F},\;\ell\in [k]\}$. We prove $C_k\subset C$ by induction on $k$. $C_0=\{\alpha\}\subset C$. If $x=c_{k+1}\circ c_k\circ\cdots\circ c_1(\alpha)\in C_{k+1}$, then $x=f(x')$ with $f=c_{k+1}\in \mathcal{F}$, $x'=c_k\circ\cdots\circ c_1(\alpha)\in C_{k}\subset C$, the latter by induction assumption. Therefore, $x\in f(C)\subset C$. 

For $C\subset C'$, we apply the Algorithm to $x\in C$. The condition in the while loop can be checked because $\mathcal{F}$ is finite and $x'$ must be smaller than $x$ by virtue of \eqref{eqn:increasing}. The algorithm terminates because $x$ is getting strictly smaller in each iteration of the while loop. The output of $c=c_k\ldots c_1$ then provides the representation of $x$ as an element of $C'$, i.e., $x=c_k\circ\cdots\circ c_1(\alpha)$.

\renewcommand{\thealgorithm}{}

\begin{algorithm}[htb!]
\begin{algorithmic}
\PROCEDURE{$C\subset C'$}
\PARAMETER{$x$} element of $C$
\\
\PARAMETER{$c$} string of elements of $\mathcal{F}$
\\
{\bf input} $x$
\\
$c\leftarrow {\epsilon}$  (empty word)
\\
{\bf while} $\exists\,f\in \mathcal{F}\;\exists\,x'\in C:x=f(x')$
\\
\quad  $x\leftarrow x',\;c\leftarrow cf$
\\
{\bf end while} 
\\
{\bf output} $c$
\end{algorithmic}
\caption{}
\label{al:A}
\end{algorithm}

{2}.~$\Rightarrow$ {3}. Let $C=\{c_k\circ \cdots\circ c_1(\alpha)\ |\ c_\ell\in \mathcal{F},\;\ell\in [k],\;k\in\mathbb{N}_0\}$ and $C'=\bigcap\{\Gamma\subset\mathbb{N}\ |\ \Gamma\;{\rm fulfills}\;{\rm SG}(\alpha,\mathcal{F})\}$. For every $\Gamma\subset\mathbb{N}$ which fulfills ${\rm SG}(\alpha,\mathcal{F})$ we can prove $C_k\subset \Gamma$ by induction as before. So $C_k\subset C'$ and consequently $C\subset C'$. Obviously, $C$ fulfills ${\rm SG}(\alpha,\mathcal{F})$, so that $C'\subset C$.

{3}.~$\Rightarrow$ {4}. $C=\bigcap\{\Gamma\subset\mathbb{N}\ |\ \Gamma\;{\rm fulfills}\;{\rm SG}(\alpha,\mathcal{F})\}$ fulfills ${\rm SG}(\alpha,\mathcal{F})$. If $\Gamma\subset\mathbb{N}$ fulfills ${\rm SG}(\alpha,\mathcal{F})$, then $C\subset \Gamma$.

{4}.~$\Rightarrow$ {1}. Let $C$ be the smallest subset of $\mathbb{N}$ that fulfills ${\rm SG}(\alpha,\mathcal{F})$ and assume that $x\in C\setminus (\{\alpha\}\cup\,\bigcup\{f(C)\ |\ f\in \mathcal{F}\})$. Let $C':=C\setminus\{x\}$. Then $\alpha\in C'$ and if $f\in \mathcal{F}$ and $x'\in C'$, then $f(x')\neq x$, i.e., $f(x')\in C'$. So $C'$ fulfills ${\rm SG}(\alpha,\mathcal{F})$, but is smaller than $C$, a contradiction.
\end{proof}


\section{Sierpi\'{n}ski graphs}\label{sec:sierpinski}

For $p\in\mathbb{N}$, $p\geq 2$, and $n\in\mathbb{N}_0$ we define Sierpi\'{n}ski graph $S_p^n$ with $V(S_p^n)=P^n$ and edge set as in \eqref{eqn:defedge}. Let $m\in\mathbb{N}$. An {\em m-key vertex} in $S_p^n$ is an $s\in P^n$ with $\dd(s,(p-1)^n)=m\cdot \dd(s,0^n)$. If $s$ is an $m$-key vertex, the value $\dd(s,0^n)$ is called an {\em m-key distance}. If there is no doubt about the $m$ we just write ``key vertex (distance)''. 
The set of $m$-key vertices in $S_p^{n}$ is denoted by $_m\Psi_{p,n}$, occasionally without the indices $m$ or $p$. A special case is $n=0$, where the only vertex ${\epsilon}$ is a key vertex for every $m$, i.e., $_m\Psi_{p,0}=\{{\epsilon}\}$, and $0$ is the only key distance. For $n\in\mathbb{N}$, key distances are always positive. 

In the discussion of the case $p=2$, Mersenne numbers $M_n=2^n-1$ play a central role. The following is probably well-known:

\begin{lemma}\label{lem:dividemersenne}
Every odd $k&gt;1$ divides some $M_\kappa$ with $\left\lceil \ln(k+1)/\ln(2) \right\rceil\leq\kappa &lt; k$. In particular, every odd number is a proper divisor of some Mersenne number.
\end{lemma}

\begin{proof} It suffices to prove the first statement because Mersenne number $M_\kappa$ is a proper divisor of $M_{2\kappa}=(2^\kappa +1)M_\kappa$ for $\kappa\in\mathbb{N}$.

The set of residues modulo $k$ of powers of 2 has size at most $k-1$ because $k&gt;1$ is odd and therefore the remainder 0 is impossible. So by the pigeonhole principle there must be $0\leq i&lt;j\leq k-1$ such that $\frac{2^j}{k}-\frac{2^i}{k}\in\mathbb{N}$, whence $k\,|\,2^i(2^{j-i}-1)$. Again because $k$ is odd we get $k\,|\,2^\kappa-1$ with $1\leq\kappa:=j-i\leq k-1$.
\end{proof}

As we have seen before, $S_2^n$, $n\in\mathbb{N}$, is a path graph on $2^n$ vertices which can be labeled by binary strings $s\in \{0,1\}^n$,  leading from $0^n$ to $1^n$ in natural order of their values as binary numbers. An $m$-key vertex $s$ must therefore satisfy $(m+1)\delta=M_n$, where the $m$-key distance $\delta$ is $\dd(s,0^n)=(s)_2$ and must be odd. We get
$$
1\leq \delta=\frac{M_n}{m+1}\leq \frac{M_n}{2},\;n\geq 2.
$$
So we find $m$-key vertices if and only if $m+1&gt;1$ is a divisor of $M_n$ and $\delta$ is a proper divisor of $M_n$.  From Lemma~\ref{lem:dividemersenne} we see that there are $m$-key vertices iff $m$ is even and that every odd $\delta$ is a key distance. We call $\delta=1$ {\em trivial}, which leads to an $(M_n-1)$-key distance with trivial key vertex $0^{n-1}1$. Note that 

\begin{center}
$M_n$ {\em is prime if and only if no non-trivial key vertex exists in} $S_2^n$.
\end{center}

So for odd $m$ and $n\in\mathbb{N}$ we have $_m\Psi_{2,n}=\emptyset$. For $m=2$ we get $_2\Psi_{2,n}=\left\{(01)^{n/2}\right\}$, if $n$ is even and $_2\Psi_{2,n}=\emptyset$, if $n$ is odd. This reflects the famous formula $M_n\bmod 3= n\bmod 2$ (cf.~\cite[p.~100]{hinz-2013}). For $n=2\nu$, $\nu\in\mathbb{N}$, the (positive) 2-key distances form the sequence \seqnum{A002450} of odd Lichtenberg numbers $\ell_{2\nu-1}=\frac{1}{3}(2^{2\nu}-1)=\dd\left((01)^\nu,0^{2\nu}\right)$. (For the {\em Lichtenberg sequence} (\seqnum{A000975}), see~\cite{hinz-2017} and \cite{paul-2017}). 
For $m=4$ we note that $5\,|\,M_n\Leftrightarrow 4\,|\,n$, as can be seen by looking at the residues modulo 5 of powers of 2, so that there are 4-key vertices if and only if $n=4\nu$, $\nu\in\mathbb{N}_0$, namely $_4\Psi_{2,4\nu}=\left\{(0011)^{\nu}\right\}$. The sequence of 4-key distances is $\seqnum{A182512}(\nu)=\frac{1}{5}(2^{4\nu}-1)=0,3,51,819,13107,\ldots\;$. 


 
\subsection{The case $m=1$}\label{sec:Sm1}
 
As a warm-up for general $p$ we ask whether for some {\em key vertices} $s\in P^n$, $n\in\mathbb{N}$,  the distances to two extreme vertices, $0^n$ and $(p-1)^n$ say, are equal.  From \eqref{eqn:invariant} we see that this cannot happen for $p=2$. For $p\geq 3$ we have from \eqref{eqn:distextreme}:
\begin{eqnarray*}
\dd(s,(p-1)^n)=\dd(s,0^n) &amp; \Leftrightarrow &amp; \sum_{d=1}^n (s_d\neq p-1)\cdot 2^{d-1} = \sum_{d=1}^n (s_d\neq 0)\cdot 2^{d-1}\\
         &amp; \Leftrightarrow &amp; \forall\,d\in [n]:s_d\neq p-1\Leftrightarrow s_d\neq 0\\
         &amp; \Leftrightarrow &amp; \forall\,d\in [n]:s_d\in [p-2]\\
         &amp; \Leftrightarrow &amp; s\in [p-2]^n.
\end{eqnarray*}
    

\begin{theorem}\label{thm:equaldist} For $p\in\mathbb{N}$, $p\geq 2$, and $n\in\mathbb{N}_0$ we have $_1\Psi_{p,n}=[p-2]^n$.
\end{theorem}

So there are $(p-2)^n$ key vertices and the corresponding {\em key distance} $\dd(s,0^n)$ is always $2^n-1$. In particular, for $p=3$ there is only one key vertex at distance $2^n-1$ from both $0^n$ and $2^n$, namely extreme vertex $1^n$.

\subsection{The case $m=2$}\label{sec:Sm2}

The {\em Fibonacci sequence} turns up in $|_2\Psi_{3,n}|=F_{n-1}$, which is also the number of 2-key distances occurring for $S_p^{n}$; see Proposition~\ref{prop:keyfibonacci} below. (This is formally compatible for $n=0$, if we put $F_{-1}=1$.) In order to generalize this result
we define $F_{q,n}$ for $q,n\in\mathbb{N}_0$ by
\begin{eqnarray}\label{eqn:lucasseq}
F_{q,0} &amp; = &amp; 0,\\ 
\label{eqn:lucasseq1}
F_{q,1} &amp; = &amp; 1,\\
\label{eqn:lucasseq2}
F_{q,n+2} &amp; = &amp; q\cdot F_{q,n+1} + F_{q,n} .
\end{eqnarray}
($F_q$ is the {\em Lucas sequence of the first kind} $U(P,Q)$ for the parameters $P=q$ and $Q=-1$; see \cite[formula (10)]{lucas-1878}. The numbers $F_{q,n}$ are sometimes called {\em $q$-Fibonacci numbers}, as, e.g., in \cite{falcon-2007}.)
Again, for formal reasons, we put $F_{q,-1}=1$, compatible with \eqref{eqn:lucasseq}, \eqref{eqn:lucasseq1}, and \eqref{eqn:lucasseq2} for $n=-1$.
Special cases are 
\begin{eqnarray*}\label{eqn:speciallucasseq}
F_{0,n} &amp; = &amp; n\bmod 2,\\
F_{1,n} &amp; = &amp; F_n,\\
F_{2,n} &amp; = &amp; P_n ,
\end{eqnarray*}
where $F_n$ are the {\em Fibonacci numbers} (\seqnum{A000045}) and $P_n$ are the {\em Pell numbers} (\seqnum{A000129}), respectively. 
Let $Q_\pm:=\frac{1}{2}\left(q\pm \sqrt{4+q^2}\right)$; then
\begin{eqnarray}\label{eqn:fibonaccirecurrence}
F_{q,n} &amp; = &amp; \frac{1}{\sqrt{4+q^2}}\left((F_{q,1}-Q_-F_{q,0})Q_+^n-(F_{q,1}-
Q_+F_{q,0})Q_-^n\right)\\
&amp; = &amp; \frac{Q_+^n-Q_-^n}{Q_+-Q_-}\notag
\end{eqnarray}
is the solution of \eqref{eqn:lucasseq2}, the latter if \eqref{eqn:lucasseq} and \eqref{eqn:lucasseq1} are fulfilled.
For $q\in\mathbb{N}$ the ratios $F_{q,n+1}/F_{q,n}$ tend to $Q_+$ as $n\rightarrow \infty$. These irrational numbers have recently been called {\em metallic means}; see, e.g., \cite[p.~2]{grubb-2021}. Since this expression is used inconsistently in literature, we prefer to refer to them as
{\em precious metal means} as, e.g., the golden ($q=1$, $Q_+=\frac{1}{2}\left(1+\sqrt{5}\right)$), silver ($q=2$, $Q_+=1+\sqrt{2}$) and bronze ($q=3$, $Q_+=\frac{1}{2}\left(3+\sqrt{13}\right)$) ratio. They have the constant infinite continued fraction representation $[q;\overline{q}]$.



Our first main result now reads

\begin{theorem}\label{thm:paulsgem} For $p\in\mathbb{N}$, $p\geq 2$, and $n\in\mathbb{N}_0$ we have $|_2\Psi_{p,n}|=F_{p-2,n-1}$.
\end{theorem}

\begin{proof} Let $\overline{s}=s_n\ldots s_1\in P^n$ and $s=s_{n+1}\overline{s}\in \Psi_{n+1}$. Then $s_{n+1}=0$, because $(p-1)^{n+1}$ is the closest extreme vertex to vertex $(p-1)\overline{s}$ in $S_p^{n+1}$ and if $s_{n+1}\in [p-2]$, then 
$$
\dd(s,(p-1)^{n+1})=\dd(\overline{s},(p-1)^n)+2^n&lt;2^{n+1}
$$
and 
$$
\dd(s,0^{n+1})=\dd(\overline{s},0^n)+2^n\geq 2^{n}.
$$

Let $\Phi_n:=\left\{s\in P^n\ |\ 2^n+\dd(s,(p-1)^n)=2\cdot\dd(s,0^n)\right\}$, i.e., $\Psi_{n+1}=0\Phi_n$. We show that $|\Phi_n|$ fulfills the recurrence \eqref{eqn:lucasseq}, \eqref{eqn:lucasseq1}, \eqref{eqn:lucasseq2} for $q=p-2$. If $s\in \Phi_0$, then $1=0$, whence $|\Phi_0|=0$, i.e., \eqref{eqn:lucasseq} holds. So let $n\in\mathbb{N}$. Then
\begin{eqnarray}\label{eqn:srecurrence}
s\in\Phi_n &amp;\Leftrightarrow &amp; 2^n+\sum_{d=1}^n (s_d\neq p-1)\cdot 2^{d-1}=2\cdot\sum_{d=1}^n(s_d\neq 0)\cdot 2^{d-1} \notag\\
&amp; \Leftrightarrow &amp; 2^n+\sum_{d=1}^{n-1} (s_{d+1}\neq p-1)\cdot 2^{d}+ (s_1\neq p-1)
=(s_n\neq 0)\cdot 2^n +\sum_{d=1}^{n-1}(s_d\neq 0)\cdot 2^{d}\notag\\
&amp; \Leftrightarrow &amp; s_1=p-1,\;\forall\,d\in [n-1]:\,s_d=0\Leftrightarrow s_{d+1}=p-1,\;s_n\neq 0.
\end{eqnarray}
For $n=1$ we have $s\in\Phi_1$ iff $s=p-1$, so $|\Phi_1|=1$, i.e., \eqref{eqn:lucasseq1} is satisfied. 
Together with \eqref{eqn:srecurrence} (cf.~also the standard drawings of $S_p^n$, e.g., in \cite[Chapter~4]{hinz-2013}) we can deduce
$$
\forall\,n\in\mathbb{N}_0:\Phi_{n+2}=[p-2]\Phi_{n+1}\,\cupdot\,(p-1)0\Phi_n.
$$
Therefore $|\Phi_n|$ also satisfies \eqref{eqn:lucasseq2} for $q=p-2$. 
\end{proof}

\begin{remark}
1. 2-key vertices $s$ lie at $\frac{2}{3}=\left(0.\overline{10}\,\right)_2$ on the only optimal path from $(p-1)^{n}$ to $0^{n}$ which passes $s$.

2. For $p=2$ it follows immediately from \eqref{eqn:srecurrence} that $\Psi_n=\emptyset$, if $n$ is odd, and that otherwise $s=(01)^{n/2}$ is the only element of $\Psi_n$, as we have seen before. 

Sierpi\'{n}ski graph $S_2^n$ and $R^n$, the state graph of the Chinese Rings (see~\cite[Chapter~2]{hinz-2013}), being isomorphic, we see that if the number of rings is odd,   there is no state at $\frac{2}{3}$ distance between the extreme states $0^n$ and $10^{n-1}$, while for an even positive number of rings there is exactly one, which is the state $1^n$. 
\qed
\end{remark}

The approach taken in \cite{hinz-2019} was slightly different. We looked at the binary representation of the key distance $\dd(s,0^{n+1})$ and observed \cite[Lemma~3.2(2)]{hinz-2019} that the last bit is 1 and that the representation does not contain a square 00 \cite[Lemma~3.2(3)]{hinz-2019} (this would, e.g., contradict the distance formula \eqref{eqn:distextreme}, because there would be a 0 at the same place in the binary representations of $\dd(s,0^{n+1})$ and $\dd(s,(p-1)^{n+1})$; for $p=2$ there are no squares 11 either because there are only two types of bits). Conversely, every binary number with these properties represents some $\dd(s,0^{n+1})$. To achieve this, one can construct a bijection between $P^n$ and the set of those binary matrices $b=(b_{j,d-1})_{j\in P,d\in [n]}\in \{0,1\}^{p\times n}$ which satisfies
\begin{equation}\label{eqn:columnsum}
\forall\,d\in [n]:\sum_{i=0}^{p-1} b_{i,d-1} = p-1;
\end{equation}
in fact, $b_{j,d-1}=(s_d\neq j)$ for $s\in P^n$. This can be based on the fact that the set of those binary matrices which satisfy \eqref{eqn:columnsum} has size $p^n$ (as can easily be seen by induction on $n$).

Note that this bijection shows that $p-1$ rows of the matrix suffice to recover $s$, because the missing row can be reconstructed by virtue of \eqref{eqn:columnsum}. Moreover, from this representation one can immediately deduce \cite[Corollary~4.7]{hinz-2013}.

Let us add our observations that $s_{n+1}=0$ for key vertices $s=s_{n+1}\overline{s}$ in $S_p^{n+1}$ \cite[Lemma~3.2(1)]{hinz-2019} and that therefore the first and last bits of $\dd(\overline{s},0^n)$ are 1. The quest for key distances in $S_p^{n+1}$ can then be reduced, for $p\geq 3$, to the problem of finding, for $n\geq 2$, the value of $|B_{n-2}|$ for the sets $B_\ell$ defined as the sets of bit strings of length $\ell\in\mathbb{N}_0$ which do not contain the substring~$00$. A counting like this can be found in \cite[Section~1.2]{benjamin-2003}. Quite obviously, $B_0$ just contains the empty word, and $B_1=\{0,1\}$. As before, we get 
$$
B_{\ell+2}=\{1t\ |\ t\in B_{\ell+1}\}\,\cupdot\,\{01t\ |\ t\in B_\ell\},
$$
whence $|B_\ell|=F_{\ell+2}$. 


The elements of the union of the $B_\ell$, $\ell\in\mathbb{N}$, considered as decimal numbers, form the sequence $a$ given by
$$
a_0=0,\;\forall\,n\in\mathbb{N},\;n\geq 2\;\forall k\in [F_n]_0:a_{F_{n+1}-1+k}=a_{F_{n-1}-1+k}+2^{n-2};
$$
this is, apart from the offset, the sequence \seqnum{A003754} of the OEIS, i.e., $a_n=\seqnum{A003754}(n+1)$ for $n\in\mathbb{N}_0$.

The distances occurring in $C_n:=\{\dd(s,0^n)\ |\ s\in \Phi_n\}$ are none for $n=0$, $(1)_2$ for $n=1$, and $(1\beta 1)_2$ with $\beta$ running through $B_{n-2}$ for $n\geq 2$ or, in other words, $C_{n}=2^{n-1}+(C_{n-1}\cup C_{n-2})$.
Hence these distances are all different so that $|C_n|=F_n$. We arrive at

\begin{proposition}\label{prop:keyfibonacci}
The number of 2-key distances in $S_p^n$, $p\geq 3$, is $F_{n-1}$.
\end{proposition}

The sequence $c$ obtained from $\Dst{\bigcup_{n\in\mathbb{N}_0} C_n}$, ordered by size, is given by $c_n=2a_{n-1}+1$ for $n\in\mathbb{N}$, i.e.,
$$
c_0=0,\;
\forall\,n\in\mathbb{N}\;\forall k\in [F_n]_0:c_{F_{n+1}+k}=c_{F_{n-1}+k}+2^{n-1}.
$$
It is $\seqnum{A247648}=2\cdot \seqnum{A003754}+1$ and starts $(0,)1, 3, 5, 7, 11, 13, 15, 21, 23, 27, \ldots$; see \cite[p.~77]{hinz-2019}. The sequence forms the self-generating set obtained from $\alpha=1$ and $\mathcal{F}=\{k\mapsto 2k+1,k\mapsto 4k+1\}$ in Lemma~\ref{lem:selfgen}. In particular, the sequence  $c$ includes the odd Lichtenberg numbers, i.e., the positive 2-key distances for $p=2$, which are generated by $k\mapsto 4k+1$ with seed 1.

The sets $\Phi_n$ contain, for $p\in\mathbb{N}$, $p\geq 3$, and $n\in\mathbb{N}$, the vertices $s\in [p-2]^{n-1}(p-1)$ with maximal distance $\dd(s,0^n)=2^n-1$. Similarly, the vertices $s=\left((p-1)0\right)^{(n-1)/2}(p-1)$, if $n$ is odd, and $s\in\left((p-1)0\right)^{(n-2)/2}[p-2](p-1)$, if $n$ is even, have minimal distance $\dd(s,0^n)=J_{n+1}$ ({\em Jacobsthal numbers} (\seqnum{A001045}); cf.~\cite{hinz-2017}). For $p=3$ it is possible to prove that all elements of $\Phi_n$ are those which lie on the straight line joining maximal distance with minimal distance vertices in the standard triangular drawing of $S_3^n$. If the side length of the triangle is chosen to be 1, this {\em magic line} is the same for all $n$ \cite[Theorem~3.3]{hinz-2019} and leads to a fractal if intersected with the Sierpi\'{n}ski triangle (of side length~1), see~\cite[Section~4]{hinz-2019}. When drawn as tetrahedra with side length~1, the graphs $S_4^n$ contain an analogue {\em magic triangle} accommodating all 2-key vertices and leading to another fascinating fractal structure, the {\em Pell fractal} (cf.~\cite[Section~5]{hinz-2019}).



\subsection{The case $m=3$}\label{sec:Sm3}

A 3-key vertex $s$ of $S_p^n$ must satisfy
\begin{equation}\label{eqn:misthree1}
\sum_{d=1}^n (s_d\neq p-1)\cdot 2^{d-1}=3\sum_{d=1}^n (s_d\neq 0)\cdot 2^{d-1}.
\end{equation}
If $s_n\neq 0$, then $\RHS\geq 3\cdot 2^{n-1}&gt;M_n\geq \LHS$; therefore $s_n=0$ and \eqref{eqn:misthree1} can be replaced by
\begin{equation}\label{eqn:misthree2}
2^{n-1}+\sum_{d=1}^{n-1} (s_d\neq p-1)\cdot 2^{d-1}=3\sum_{d=1}^{n-1} (s_d\neq 0)\cdot 2^{d-1}.
\end{equation}
For $n=1$ this leads to a contradiction, whence $_3\Psi_{p,1}=\emptyset$. So let $n\geq 2$ and assume that $s_{n-1}=0$. Then $\RHS\leq 3\cdot M_{n-2}&lt;3\cdot 2^{n-2}=2^{n-1}+2^{n-2}\leq \LHS$, a contradiction. Similarly, if $s_{n-1}=p-1$, then $\LHS\leq 2^{n-1}+M_{n-1}&lt; 3\cdot 2^{n-2}\leq \RHS$, another contradiction. Therefore, $s_{n-1}\in [p-2]$ and \eqref{eqn:misthree2} reduces to
\begin{equation}\label{eqn:misthree3}
\sum_{d=1}^{n-2} (s_d\neq p-1)\cdot 2^{d-1}=3\sum_{d=1}^{n-2} (s_d\neq 0)\cdot 2^{d-1}.
\end{equation}
For $n=2$ we are done with $_3\Psi_{p,2}=0[p-2]$. For $n\geq 3$ we notice that \eqref{eqn:misthree3} is the same as \eqref{eqn:misthree1}, but with $n$ replaced by $n-2$. It follows that
$$
_3\Psi_{p,n}=0[p-2]\,{_3\Psi_{p,n-2}}
$$
with $\dd(s,(p-1)^n)=M_n$ for $s\in{_3\Psi_{p,n}}$.
We can summarize the case $m=3$ in the following theorem.
\begin{theorem}\label{thm:mis3}
The set of $3$-key vertices in $S_p^n$ is empty for odd $n$ and otherwise $_3\Psi_{p,n}=(0[p-2])^{n/2}$ with $|_3\Psi_{p,n}|=(p-2)^{n/2}$. The sequence of positive $3$-key distances is $\frac{1}{3}M_{2k}=\ell_{2k-1}=1,5,21,85,\ldots$ for $k\in\mathbb{N}$; these are the odd Lichtenberg numbers, \seqnum{A002450}. It is the self-generating sequence for seed~$1$ and generating function set $\{k\mapsto 4k+1\}$.
\end{theorem}



\subsection{The case $m=4$}\label{sec:Sm4}

For this case we need some preparation.
 For $q\in\mathbb{N}_0$ let the sequences $(FF_{q,n})_{n\in\mathbb{N}_0}$ be defined by 
\begin{eqnarray}\label{eqn:llucasseq}
FF_{q,0}\,=\,FF_{q,1}\,=\,FF_{q,2} &amp; = &amp; 0,\\ 
\label{eqn:llucasseq1}
FF_{q,3} &amp; = &amp; 1,\\
\label{eqn:llucasseq2}
FF_{q,n+4} &amp; = &amp; q\left(FF_{q,n+3}+FF_{q,n+1}\right)+FF_{q,n}.
\end{eqnarray}
As before and consistent with \eqref{eqn:llucasseq}, \eqref{eqn:llucasseq1} and \eqref{eqn:llucasseq2}, we put $FF_{q,-1}=1$.
For $q=0$, the sequence is $FF_{0,n}=(n\mod 4=3)$. If $q=1$, we write $FF_n$ for $FF_{1,n}$; then the sequence $FF_{3+n}$ is \seqnum{A006498}. The sequence of differences $\overline{FF}$ is, apart from the shift of the offset, \seqnum{A070550}. For the sequence of partial sums $\Sigma FF$, cf.~the somewhat obscure entry \seqnum{A097083} of the OEIS. The sequences $FF_{2,n}$ and $FF_{3,n}$ are, but for the offsets, \seqnum{A089928} and \seqnum{A089931}, respectively. The relation between the sequences $FF_{q,n}$ and $F_{q,n}$ is the following.

\begin{proposition}\label{prop:fftof} For all $q,k\in\mathbb{N}_0$:
$FF_{q,2k}=F_{q,k-1}F_{q,k},\;FF_{q,2k+1}=F_{q,k}^2.$
\end{proposition}

\proof Induction on $k$, where the cases $k=0$ and $k=1$ are obvious. For $k\in\mathbb{N}$ we get:
\begin{align*}
FF_{q,2(k+1)} = FF_{q,2(k-1)+4} &amp; = q\cdot FF_{q,2(k-1)+3}+q\cdot FF_{q,2(k-1)+1}+FF_{q,2(k-1)}\\
&amp; =  q\cdot F_{q,k}^2+q\cdot F_{q,k-1}^2+F_{q,k-2}F_{q,k-1}\\
&amp; = q\cdot  F_{q,k}^2+F_{q,k-1}(q\cdot F_{q,k-1}+F_{q,k-2})\\
&amp; = q\cdot F_{q,k}^2+F_{q,k-1}F_{q,k} = F_{q,k}F_{q,k+1}
\end{align*}
and
\begin{align*}
FF_{q,2(k+1)+1} = FF_{q,2k-1+4} &amp; = q\cdot FF_{q,2k+2}+q\cdot FF_{q,2k}+FF_{q,2k-1}\\
&amp; = q\cdot FF_{q,2(k+1)}+q\cdot FF_{q,2k}+FF_{q,2(k-1)+1} \\
&amp; = q\cdot F_{q,k}F_{q,k+1}+q\cdot F_{q,k-1}F_{q,k}+F_{q,k-1}^2\\
&amp; = q\cdot F_{q,k}F_{q,k+1}+F_{q,k-1}F_{q,k+1}=F_{q,k+1}^2. \tag*{\qed}
\end{align*}

In particular,  for all $k\in \mathbb{N}_0$ we have
$$
\begin{array}{l}
    FF_{1,2k}  = F_{k}\cdot F_{k-1},\\ 
    FF_{1,2k+1}  = F_{k}^2
\end{array}
 \mbox{\qquad and \qquad}
\begin{array}{l}
    FF_{2,2k}  = P_{k}\cdot P_{k-1},\\ 
    FF_{2,2k+1}  = P_{k}^2.
\end{array}
$$


We will now set out to prove

\begin{theorem}\label{thm:paulsgemforfour} For $p\in\mathbb{N}$, $p\geq 2$, and $n\in\mathbb{N}_0$ we have $|_4\Psi_{p,n}|=FF_{p-2,n-1}$.
\end{theorem}

\begin{proof} For $n=0$, we have $_4\Psi_{p,0}=\{{\epsilon}\}$, whence $|_4\Psi_{p,0}|=1=FF_{p-2,-1}$ by our convention. In $S_p^1\cong K_p$ there is no distance four times a different one, so $_4\Psi_{p,1}=\emptyset$ and $|_4\Psi_{p,1}|=0=FF_{p-2,0}$. For $n\geq 2$ we have that $s\in P^n$ lies in $_4\Psi_{p,n}$ iff
\begin{eqnarray*}
(s_1\neq p-1) &amp; + &amp; (s_2\neq p-1)\cdot 2 \;\; + \;\; \sum_{d=3}^n(s_d\neq p-1)\cdot 2^{d-1}\\
&amp; = &amp;
\sum_{d=3}^n(s_{d-2}\neq 0)\cdot 2^{d-1}+(s_{n-1}\neq 0)\cdot 2^n+(s_n\neq 0)\cdot 2^{n+1}.
\end{eqnarray*}
This, in turn, is only possible if
$$
s_1=p-1=s_2,\;\forall\,d\in [n-2]:s_d=0\Leftrightarrow s_{d+2}=p-1,\;s_{n-1}=0=s_n.
$$
For $n=2$ and $n=3$ this cannot be fulfilled, so $_4\Psi_{p,2}=\emptyset ={_4\Psi_{p,3}}$ and consequently $|_4\Psi_{p,2}|= 0 =FF_{p-2,1}$ and $|_4\Psi_{p,3}|= 0 =FF_{p-2,2}$. For $n\geq 4$ this amounts to $s=00\overline{s}(p-1)(p-1)$ with $\overline{s}=s_{n-2}\ldots s_3\in P^{n-4}$ fulfilling 
\begin{equation}\label{eqn:4keycondition2}
s_3\neq p-1\neq s_4,\;\forall\,d\in [n-4]\setminus [2]:s_d=0\Leftrightarrow s_{d+2}=p-1,\;s_{n-3}\neq 0\neq s_{n-2}.
\end{equation}
Let $\overline{S}_1=\overline{S}_2=\overline{S}_3=\emptyset$ and for $n\geq 4$ denote the set of $\overline{s}$ fulfilling \eqref{eqn:4keycondition2} by $\overline{S}_n$. Then $\overline{S}_4=\{{\epsilon}\}$, $\overline{S}_5=[p-2]$, $\overline{S}_6=[p-2]^2$, and $\overline{S}_7=[p-2]^3\,\cupdot\,(p-1)[p-2]0$.
For $n\geq 8$ we have the following three cases for an $\overline{s}=s_{n-2}s_{n-3}\ldots s_3\in \overline{S}_{n}$, depending on the number of initial $p-1$ (there cannot be three in a row because of \eqref{eqn:4keycondition2}):
\begin{enumerate}
\item $0\neq s_{n-2}\neq p-1$,
\item $s_{n-2}=p-1\neq s_{n-3}\neq 0$,
\item $s_{n-2}=p-1=s_{n-3}$.
\end{enumerate}
In case~1, $\overline{s}$ will run through $[p-2]\overline{S}_{n-1}$, because $s_{n-3}\neq 0 \neq s_{n-4}$. In case~2, $s_{n-4}$ has to be 0, and all elements of $(p-1)[p-2]0\overline{S}_{n-3}$ are admissible because $s_{n-5}\neq 0 \neq s_{n-6}$. Finally, in case~3, $s_{n-4}=0=s_{n-5}$, and all elements of $(p-1)(p-1)00\overline{S}_{n-4}$ are admissible because $s_{n-6}\neq 0 \neq s_{n-7}$. So we obtain that for $n\geq 8$ (in fact, for $n\geq 5$):
\begin{equation}\label{eqn:Scondition}
\overline{S}_n=[p-2]\overline{S}_{n-1}\cup (p-1)[p-2]0\overline{S}_{n-3}\cup (p-1)(p-1)00\overline{S}_{n-4},
\end{equation}
with the unions disjoint. We can conclude that (for $n\in\mathbb{N}$)
\begin{eqnarray}\label{eqn:Slucasseq}
|\overline{S}_1|\,=\,|\overline{S}_2|\,=\,|\overline{S}_3| &amp; = &amp; 0,\\
\label{eqn:Slucasseq1}
|\overline{S}_4| &amp; = &amp; 1,\\
\label{eqn:Slucasseq2}
|\overline{S}_{n+4}| &amp; = &amp; (p-2)\left(|\overline{S}_{n+3}|+|\overline{S}_{n+1}|\right)+|\overline{S}_{n}|.
\end{eqnarray}
Comparison of \eqref{eqn:Slucasseq}, \eqref{eqn:Slucasseq1}, \eqref{eqn:Slucasseq2} with \eqref{eqn:llucasseq}, \eqref{eqn:llucasseq1}, \eqref{eqn:llucasseq2} yields $|\overline{S}_{n}|=FF_{p-2,n-1}$ and since $|_4\Psi_{p,n}|=|\overline{S}_{n}|$, the theorem is proved.
\end{proof}

If we ask for $DD_n:=\{\dd(s,0^n)\ |\ s\in {_4\Psi_{p,n}\}}$, we see that $DD_0=\{0\}$, $DD_1=DD_2=DD_3=\emptyset$, and for $n\geq 4$ we have
\begin{equation}\label{eqn:DDn}
DD_n=3+\left\{\sum_{d=3}^{n-2}(s_d\neq 0)\cdot 2^{d-1}\ |\ \overline{s}=s_{n-2}\ldots s_3\in\overline{S}_n\right\}.
\end{equation}
All elements of $\overline{S}_n$ have the form $\sigma=\sigma_k\ldots\sigma_1$, where $\sigma_\ell\in [p-2]\,\cupdot\,(p-1)[p-2]0\,\cupdot\,\{(p-1)(p-1)00\}$ and $k\in\mathbb{N}_0$ is such that $\sigma$ has overall length $n$.
It follows that the binary representation of a distance in $DD_n$ has the form $00\beta_k\ldots \beta_111$ with $\beta_\ell=1$ if $\sigma_\ell\in [p-2]$, $\beta_\ell=110$ if $\sigma_\ell\in (p-1)[p-2]0$, and $\beta_\ell=1100$ if $\sigma_\ell= (p-1)(p-1)00$, respectively. Therefore, $\max DD_n=M_{n-2}$, if $p&gt;2$; $\max DD_n=\frac{1}{5}M_n=\min DD_n$, if $p=2$ and $n\mod 4=0$ (this is \seqnum{A182512}; cf.~supra);
and finally, for $p&gt;2$,
\begin{displaymath}
  \min DD_n = \begin{cases}
                  (00(1100)^{(n-4)/4}11)_{2} = \frac{1}{5}(2^n-1), &amp; \text{if $n\mod 4=0\,$;}\\
                  (00(1100)^{(n-5)/4}111)_{2} = \frac{1}{5}(2^n+3), &amp; \text{if $n\mod 4=1\,$;}\\
                  (00(1100)^{(n-6)/4}1111)_{2} = \frac{1}{5}(2^n+11), 
&amp; \text{if $n\mod 4=2\,$;}\\
                  (00(1100)^{(n-7)/4}11011)_{2} = \frac{1}{5}(2^n+7), 
&amp; \text{if $n\mod 4=3.$}
                 \end{cases}
\end{displaymath}
Asymptotically, for large $n$, we have $\min DD_n \sim \frac{1}{5}2^n$ and $\max DD_n \sim \frac{1}{4}2^n$. Note further that for $n\geq 6$ every element of $DD_n$ has a binary representation $0011\beta 11$ with a bit string $\beta$ of length $n-6$ and which does {\em not} contain a substring $000$ or 
$010$.  From \eqref{eqn:DDn} and \eqref{eqn:Scondition} we also obtain the recurrence relation $DD_{n+4}=2^{n+1}+\left(DD_{n+3}\cup\left(2^{n}+(DD_{n+1}\cup DD_n)\right)\right)$ for $n\in\mathbb{N}_0$. The sequence $cc$ resulting from the union over $n\in\mathbb{N}$ of the sets $DD_n$ by order of size is given by $cc(1)=3$ and $\forall\,n\in\mathbb{N}_0$:
\begin{eqnarray*}
\forall\,k\in [FF_n+FF_{n+1}]: &amp; cc(\Sigma FF_{n+3}+k)=3\cdot 2^{n+1}+cc(\Sigma FF_{n-1}+k),\\
\forall\,k\in [FF_{n+3}]: &amp; cc(\Sigma FF_{n+4}-FF_{n+3}+k)=2^{n+2}+cc(\Sigma FF_{n+2}+k).
\end{eqnarray*}
The sequence $cc$ (with offset 1) starts $$3, 7, 15, 27, 31, 51, 55, 59, 63, 103, 111, 115, 119, 123, 127,\ldots$$ and is \seqnum{A353578} of the OEIS. It can be viewed as the self-generating sequence with seed 3 and generating function set $\{k\mapsto 2k+1,k\mapsto 8k+3,k\mapsto 16k+3\}$ (cf.~Lemma~\ref{lem:selfgen}).

As an example, we consider the case $n=8$. 
Theorem~\ref{thm:paulsgemforfour} and Proposition~\ref{prop:fftof} 
assert that there are $FF_{p-2,7} = F_{p-2,3}^2$ 4-key vertices.  For $p=2$ this is $(3\mod 2)^2=1$, for $p=3$ this is $F_3^2 = 2^2 = 4$, 
while for $p=4$ this is $P_3^2 = 5^2=25$.
The 4-key vertices come in four
forms:  
\begin{align*}
                &amp;0^2[p-2]^4(p-1)^2,\\
                &amp;0^2[p-2](p-1)[p-2]0(p-1)^2,\\
                &amp;0^2(p-1)[p-2]0[p-2](p-1)^2, \mbox{ and}\\
                &amp;0^2(p-1)^20^2(p-1)^2.
\end{align*}
The numbers of key vertices of these types are $(p-2)^4$, $(p-2)^2$, $(p-2)^2$, and 1, totaling 1 for $p=2$, 4 for $p=3$,
and 25 for $p=4$, as expected.  The corresponding key distances are $(00111111)_2=63=cc_9$, $(00111011)_2=59=cc_8$, $(00110111)_2=55=cc_7$, and $(00110011)_2=51=cc_6$.  Figure~\ref{fig:4key}
illustrates the four 4-key vertices 00111122, 00121022, 00210122, and 00220022 when $p=3$. 

\begin{figure}[h!]
 \centering
 \includegraphics[width=5.67in,height=5.01in,keepaspectratio]{S3,6.jpg}
 \caption{4-key vertices in $S_3^8$ (subgraph $00S_3^6$ shown)}
 \label{fig:4key}
\end{figure}


\section{Sierpi\'{n}ski triangle graphs}\label{sec:trianglegraphs}

The approximation of the Sierpi\'{n}ski triangle by a sequence of graphs is even more direct when we consider {\em Sierpi\'{n}ski triangle graphs} $\ST^n$. They are embedded as the case $p=3$ in the class $\ST_p^n$ with vertex sets 
$$
V(\ST_p^n)= \widehat{P}\cup \left\{s_\nu\ldots s_2s_1\ |\ s_\nu\ldots s_2\in P^{\nu-1},\;\nu\in [n],\;s_1=\widehat{ij},\;\{i,j\}\in \textstyle{{P\choose 2}}\right\},
$$
where $p\in\mathbb{N}$, $p\geq 2$, and $\widehat{P}$ stands for the set of {\em primitive vertices} $\widehat{k}$, $k\in P=[p]_0$; in particular, $\ST_p^0$ is the complete graph on $\widehat{P}$.
All non-primitive vertices $s_\nu\ldots s_2\widehat{ij}$ in $\ST_p^n$ come about by contracting the edge between vertices $s_\nu\ldots s_2ij^{n-\nu+1}$ and $s_\nu\ldots s_2ji^{n-\nu+1}$ in $S_p^{n+1}$; note that $\widehat{ij}=\widehat{ji}$. The primitive vertex $\widehat{k}$ corresponds to extreme vertex $k^{n+1}$, and all non-contracted edges of $S_p^{n+1}$ are preserved in $\ST_p^n$. For a direct definition of the edge set
of $\ST_p^n$, see \cite[Definition~3]{hinz-2020}. The Sierpi\'{n}ski triangle graph $\ST_p^{1+n}$ can be obtained recursively by taking $p$ copies $k\ST_p^n$ in which a $k\in P$ has been concatenated to the left of the vertices of $\ST_p^n$ and finally writing $\widehat{k}$ for $k\widehat{k}$ and identifying $k\widehat{\ell}$ and 
$\ell\widehat{k}$ for $\ell\in P$, $k\neq\ell$, resulting in {\em critical vertex} $\widehat{k\ell}$. Consequently, $\ST_p^n$ is connected; the canonical distance function is denoted by $\dd^{(n)}$.
In the case of $p=2$, we obtain a $\widehat{0},\widehat{1}$-path of length $2^n$ with the only critical vertex $\widehat{01}$. For $p=3$ we write $\ST^n:=\ST_3^n$; see Figure~\ref{fig:ST33}.
\begin{figure}[h!]
 \centering
 \includegraphics[width=5.67in,height=5.01in,keepaspectratio]{S-hat3,3.jpg}
 \caption{Drawing of the Sierpi\'{n}ski triangle graph $\ST^3$}
 \label{fig:ST33}
\end{figure}

For our purpose the distance of a vertex to a primitive vertex is of utmost importance. We have 
(cf.~\cite[Equations~(3) to (5)]{hinz-2020}):
\begin{equation}\label{eqn:distprimitive}
\dd^{(n)}(\widehat{k},\widehat{\ell})=2^n\cdot (k\neq\ell)
\end{equation}
and
\begin{eqnarray}\label{eqn:dist}
\dd^{(n)}(s_\nu\ldots s_2\widehat{ij},\widehat{\ell}) &amp; = &amp; 2^{n-\nu}\dd^{(\nu)}(s_\nu\ldots s_2\widehat{ij},\widehat{\ell}) \notag \\
&amp; = &amp;
2^{n-\nu}\left(1+(i\neq\ell\neq j)+
\sum_{d=1}^{\nu-1} (s_{d+1}\neq\ell)\cdot 2^d\right).
\end{eqnarray}

As before, we are interested in {\em m-key vertices} $s$ for which, without loss of generality, the distance to $\widehat{p-1}$ is $m$ times the distance to $\widehat{0}$. Primitive vertices $\widehat{k}$ are $m$-key vertices, iff $m=1$ and $k\in [p-2]$; the key distance is $2^n$. We write $_1\Phihat_{p,0}=\widehat{[p-2]}$ and $_m\Phihat_{p,0}=\emptyset$ for $m&gt;1$. Moreover, by \eqref{eqn:dist} it suffices to look at the case $\nu=n\in\mathbb{N}$, i.e., we consider the sets $_m\Phihat_{p,n}$ given by
$$
\left\{s\widehat{ij}\ |\ s=s_{n}\ldots s_2\in P^{n-1}, \{i,j\}\in\textstyle{{P\choose 2}};\;\dd^{(n)}(s\widehat{ij},\widehat{p-1}) 
= m\cdot \dd^{(n)}(s\widehat{ij},\widehat{0})\right\}.
$$
The set of $m$-key vertices in $\ST_p^n$ is then 
$\Psihat_{n}=\displaystyle{\bigcup_{\nu=0}^n}{_m\Phihat_{p,\nu}}$ 
and its size is 
$|\Psihat_{n}|=\Dst{\sum_{\nu=0}^n} |_m\Phihat_{p,\nu}|$.

As we already know, $\ST_2^n$ is a path graph on $2^n+1$ vertices whose leaves are the primitive vertices $\widehat{0}$ and $\widehat{1}$. A $\delta$ is an $m$-key distance iff $(m+1)\delta=2^n$, i.e., if
$$
1\leq \delta=\frac{2^n}{m+1}\leq 2^{n-1}.
$$
So $m=M_\nu$, $\nu\in [n]$, and $\delta=\dd^{(n)}(s,\widehat{0})=2^{n-\nu}$ with $m$-key vertex $s=0^{\nu-1}\widehat{01}\in V(\ST_2^\nu)\subset V(\ST_2^n)$.

\subsection{The case $m=1$}\label{sec:STm1}

For $m=1$ and $n\in\mathbb{N}$ we have
\begin{eqnarray*}
s\widehat{ij}\in\Phihat_n &amp;\Leftrightarrow &amp; 1+(i\neq p-1\neq j) + 
\sum_{d=1}^{n-1} (s_{d+1}\neq p-1)\cdot 2^{d}\\
&amp; &amp; \hspace*{35mm}
=   1+(i\neq 0\neq j)+
\sum_{d=1}^{n-1} (s_{d+1}\neq 0)\cdot 2^{d}\\
&amp; \Leftrightarrow &amp; (i\neq p-1\neq j)=(i\neq 0\neq j)\;{\rm and}\;
%\\
%&amp; &amp;  \hspace*{23mm} 
\forall\,d\in [n-1]:(s_{d+1}\neq p-1)=(s_{d+1}\neq 0)\\
&amp; \Leftrightarrow &amp; s\in [p-2]^{n-1}\;{\rm and}\;\left(\widehat{ij}=\widehat{0(p-1)}\;{\rm or}\;\{i,j\}\in \textstyle{{[p-2]\choose 2}}\right).
\end{eqnarray*}
Let $V_p:=\left\{\widehat{0(p-1)}\right\}\,\cupdot\,\left\{\widehat{ij}\ |\ \{i,j\}\in {[p-2]\choose 2}\right\}$ and $f_p:=|V_p|=1+{p-2\choose 2}$. Then we have shown:
\begin{theorem}\label{thm:STm1}
For all $p\in\mathbb{N}$, $p\geq 2$, and all $n\in\mathbb{N}_0$:
$$_1\Psihat_{p,n}=\widehat{[p-2]}\;\cupdot\;\Dst{\bigcup_{\nu=1}^n} [p-2]^{\nu-1}V_p;$$
$$\left|_1\Psihat_{3,n}\right|=1+n;\;\left|_1\Psihat_{p,n}\right|=p-2+f_p\frac{(p-2)^n-1}{p-3},\mbox{\textit{ if }}p\neq 3.$$
In particular, $_1\Psihat_{2,n}=\emptyset$ if $n=0$, $_1\Psihat_{2,n}=\{\widehat{01}\}$ otherwise; $$_1\Psihat_{3,n}=\{\widehat{1}\}\,\cupdot\,\{1^\mu\widehat{02}\ |\ \mu\in [n]_0\};\;|_1\Psihat_{4,n}|=2^{n+1}.$$
\end{theorem}

When we ask for 1-key distances, we can enter the 1-key vertices from Theorem~\ref{thm:STm1} into the distance formulas \eqref{eqn:distprimitive} and \eqref{eqn:dist}. The case $p=2$ can contribute only one value, and only for $n\neq 0$, namely $2^{n-1}$. For $p\geq 3$ we get $2^n$ and $2^n-2^{n-\nu}$, $\nu\in [n]$. These sets only overlap at powers of 2, so that the sequence of all 1-key distances is given by ${n\choose 2}+\nu\mapsto 2^n-2^{n-\nu}$ for $n\in\mathbb{N}$ and $\nu\in [n]$. These are the numbers whose binary representation is $(1^{n-\mu}0^\mu)_2$ with $\mu\in [n]_0$. They form, apart from the offset, sequence \seqnum{A023758} of the OEIS.

Figure \ref{m=1} illustrates the six key vertices in $\widehat{S}_3^5=\ST^5$  that are equidistant from primitive vertices
$\widehat{0}$ and $\widehat{2}$.  From left to right, these vertices are $\widehat{1}$ at distance 32, $1^{4-\mu}\widehat{02}$ for $\mu$ from 0 to 4 at distances $(1^{5-\mu}0^\mu)_2$, i.e., 31, 30, 28, 24, and 16, respectively.


\begin{figure}[h!] 
  \centering
  \includegraphics[width=5.67in,height=5.01in,keepaspectratio]{newS-hat.jpg}
  \caption{$m$-key vertices in $\ST^5$ for $m=1$ (red), $2$ (green), $3$ (blue), and $4$ (violet)}
  \label{m=1}
\end{figure}


\subsection{The case $m=2$}\label{sec:STm2}

For $q,n\in\mathbb{N}_0$ let us define $\widetilde{F}_{q,n}$ by
\begin{eqnarray}\label{eqn:lucasseqvar}
\widetilde{F}_{q,0} &amp; = &amp; q,\notag\\
\widetilde{F}_{q,1} &amp; = &amp; \textstyle{{q \choose 2}},\notag\\
\widetilde{F}_{q,n+2} &amp; = &amp; q\cdot \widetilde{F}_{q,n+1} + \widetilde{F}_{q,n} .
\end{eqnarray}
We notice that $\widetilde{F}_{0,n}=0$, $\widetilde{F}_{1,n+1}=F_{n}$, and $\widetilde{F}_{2,n+2}=4\cdot P_{n+1}+P_{n}=\seqnum{A048654}(n+1)$.

\begin{theorem}\label{thm:paulsgemtriangle} For $p\in\mathbb{N}$, $p\geq 2$, 
$_2\Phihat_{p,0}=\emptyset$
and for $n\in\mathbb{N}$ we have $|_2\Phihat_{p,n}|=\widetilde{F}_{p-2,n-1}$.
\end{theorem}

\begin{proof} Since 3 does not divide $2^n$, there are no 2-key vertices in $\ST_2^n$; so we may assume that $p\geq 3$.

We know already that a 2-key vertex cannot be primitive, i.e., $_2\Phihat_{p,0}=\emptyset$.  From \eqref{eqn:dist} we deduce for $n\in\mathbb{N}_0$:
\begin{eqnarray*}
s\widehat{ij}\in\,_2\Phihat_{p,n+1} &amp; \Leftrightarrow &amp; (i\neq p-1\neq j)+
\sum_{d=1}^{n} (s_{d+1}\neq p-1)\cdot 2^d \\
&amp; &amp; \hspace*{28mm} = 1+ 2(i\neq 0\neq j)+
\sum_{d=1}^{n} (s_{d+1}\neq 0)\cdot 2^{d+1}.
\end{eqnarray*}
This means that $i\neq p-1\neq j$ and that for $n=0$ we have $_2\Phihat_{p,1}=\widehat{0[p-2]}$ and consequently $|_2\Phihat_{p,1}|=p-2=\widetilde{F}_{p-2,0}$. Moreover, for $n\in\mathbb{N}$ we get $s_{n+1}=0$ so that we can reduce the problem to finding $|\Phihat_n|=|0\Phihat_n|=|_2\Phihat_{p,n+1}|$ for 
$$
\Phihat_n:=\Big\{s\widehat{ij}\ |\ s=s_{n}\ldots s_2\in P^{n-1}, \{i,j\}\in\textstyle{{P'\choose 2}};\;
2^n+\dd^{(n)}(s\widehat{ij},\widehat{p-1})=2\cdot \dd^{(n)}(s\widehat{ij},\widehat{0})\Big\},
$$
where $P':=[p-1]_0$. For completeness, we also define
$$
\Phihat_0:=\left\{\widehat{k}\ |\ k\in P,\;1+\dd^{(0)}(\widehat{k},\widehat{p-1})=2\cdot \dd^{(0)}(\widehat{k},\widehat{0})\right\}=\widehat{[p-2]},
$$
so that $|\Phihat_0|=p-2=\widetilde{F}_{p-2,0}$. Note that $0\Phihat_0=\widehat{0[p-2]}$ due to the recursive definition of $\ST_p^{1+n}$.
For $n\in\mathbb{N}$ we have
$$
s\widehat{ij}\in\Phihat_n \Leftrightarrow 
\sum_{d=1}^{n-1} (s_{d+1}\neq p-1)\cdot 2^d + 2^n= 2(i\neq 0\neq j)+
\sum_{d=1}^{n-1} (s_{d+1}\neq 0)\cdot 2^{d+1}.
$$
If $n=1$, this means that $i\neq 0\neq j$, whence $\Phihat_1=\left\{\widehat{ij}\ |\ \{i,j\}\in{[p-2]\choose 2}\right\}$, i.e., 
$|\Phihat_1|=\textstyle{{p-2\choose 2}}=\widetilde{F}_{p-2,1}$.
For $n\geq 2$ we have $s\widehat{ij}\in\Phihat_n$ if and only if
$$
s_2\neq p-1\Leftrightarrow i\neq 0\neq j,\;\forall\,d\in [n-1]\setminus \{1\}:s_{d+1}=p-1\Leftrightarrow s_d=0,\;s_n\neq 0.
$$
As in the proof of Theorem~\ref{thm:paulsgem} we can deduce from this that 
\begin{equation}\label{eqn:Phihat}
\Phihat_{n+2}=[p-2]\Phihat_{n+1}\,\cupdot\, (p-1)0\Phihat_n,
\end{equation}
so that
$|\Phihat_{n+2}|=(p-2)|\Phihat_{n+1}|+|\Phihat_n|$ for $n\in\mathbb{N}_0$, i.e., \eqref{eqn:lucasseqvar} is satisfied with $q=p-2$. 
\end{proof}

As an example, the 2-key vertices in $\ST_3^5=\ST^5$ are $\widehat{01}$, $02\widehat{01}$, $012\widehat{01}$, $0202\widehat{01}$, and $0112\widehat{01}$ (see Figure~\ref{m=1}). To see why there are exactly $5=F_5$ of them, we have to calculate $\widehat{F}_{q,n}=\Dst{\sum_{\nu=0}^{n-1} \widetilde{F}_{q,\nu}}$. It fulfills
$$
\widehat{F}_{q,0}=0,\;\widehat{F}_{q,1}=q,\;\forall\,n\in\mathbb{N}_0:\widehat{F}_{q,n+2}=-\textstyle{{q\choose 2}}+q\widehat{F}_{q,n+1}+\widehat{F}_{q,n}.
$$
This can be solved by putting $G_{q,n}=\widehat{F}_{q,n}-\frac{q-1}{2}$ which then fulfills
$$
G_{q,0}=-\textstyle{\frac{q-1}{2}},\;G_{q,1}=\textstyle{\frac{q+1}{2}},\;\forall\,n\in\mathbb{N}_0:G_{q,n+2}=qG_{q,n+1}+G_{q,n}.
$$
For $q=1$ we obtain $\widehat{F}_{1,n}=G_{1,n}=F_n$, and $q=2$ yields (cf.~\eqref{eqn:fibonaccirecurrence})
\begin{eqnarray*}
\widehat{F}_{2,n}=G_{2,n}+\textstyle{\frac{1}{2}} &amp; = &amp;
\textstyle{\frac{1}{4}}\left((2\sqrt{2}-1)(1+\sqrt{2})^n-(2\sqrt{2}+1)(1-\sqrt{2})^n+2\right) \\
&amp; = &amp;
0,2,3,7,16,38,91,219,528,\ldots\;,
\end{eqnarray*}
which is \seqnum{A353580} in the OEIS.

To find out about the {\em 2-key distances}, i.e., the distances of 2-key vertices to the primitive vertex $\widehat{0}$, we define, for $\nu,n\in\mathbb{N}_0$:
$$
D_\nu=\left\{\dd^{(\nu+1)}(s\widehat{ij},\widehat{0})\ |\ s\widehat{ij}\in
{_2\widehat{\Phi}_{p,\nu+1}}\right\}=\left\{\dd^{(\nu)}(s\widehat{ij},\widehat{0})\ |\ s\widehat{ij}\in\widehat{\Phi}_\nu\right\},
$$
the latter if $\nu\geq 1$, and
$$
B_n=\bigcup_{\nu=0}^{n-1} 2^{n-1-\nu} D_\nu=\bigcup_{\nu=0}^{n-1} 2^{\nu} D_{n-1-\nu},\;B=\bigcup_{n\in\mathbb{N}} B_n.
$$
$B_n$ is the set of distances to $\widehat{0}$ occurring among 2-key vertices in $\ST_p^n$. It fulfills the recurrence
\begin{equation}\label{eqn:Brecurrence}
B_0=\emptyset,\;\forall\,n\in\mathbb{N}_0:B_{n+1}=2B_n\cup D_n.
\end{equation}
For $\nu =0$ we have $_2\widehat{\Phi}_{p,1}=\widehat{0[p-2]}$ and $\dd^{(1)}(\widehat{0j},\widehat{0})=1$ for $j\in [p-2]$, so that $D_0=\{1\}$.
For $\nu =1$ we have $\widehat{\Phi}_{1}=\left\{\widehat{ij}\ |\ \{i,j\}\in{[p-2]\choose 2}\right\}$ and $\dd^{(1)}(\widehat{ij},\widehat{0})=2$, so that $D_1=\emptyset$, if $p=3$, and $D_1=\{2\}$, if $p\geq 4$.
Using \eqref{eqn:Phihat} we get:
\begin{equation}\label{eqn:Dn}
\forall\,n\in\mathbb{N}_0:D_{n+2}=2^{n+1}+(D_{n+1}\cup D_n).
\end{equation}
Note that for $p=3$ this is the recurrence of the sets $C_n$ (cf.~supra) with the seeds switched and that the elements of $D_n$ are the odd elements of $B_{n+1}$. Independent of $p\geq 3$ we get
\begin{equation}\label{eqn:Bn}
B_0=\emptyset,\;B_1=\{1\},\;\forall\,n\in\mathbb{N}_0:B_{n+2}=2^{n}+(B_{n+1}\cup B_n).
\end{equation}
The first two statements are clear, as is $B_2=\{2\}$ for the base step of an induction proof for the recurrence relation. The induction step is 
\begin{eqnarray*}
B_{n+3} = 2B_{n+2}\cup D_{n+2} &amp; = &amp; 2^{n+1}+(2B_{n+1}\cup 2B_n\cup D_{n+1}\cup D_n)\\
&amp; = &amp; 2^{n+1}+(B_{n+2}\cup B_{n+1}).
\end{eqnarray*}

 From equations \eqref{eqn:Dn} and \eqref{eqn:Bn} we immediately get
$$
2^{n-1}&lt;D_n\leq 2^n,\;2^{n-1}&lt;B_{n+1}\leq 2^n;
$$
in particular, the sets in the sequence $B$ are disjoint, as are those from the sequence $D$, whence
$
|D_n|=F_{n-1}$, if $p=3$,  $|D_n|=F_{n+1}$, if $p\geq 4$, and $|B_n|=F_n
$
for $n\in\mathbb{N}_0$.
More precisely:
\begin{proposition}\label{prop:propsofB}
For $n\in\mathbb{N}$ we have

\noindent{\rm (a)} $\max\,B_n=2^{n-1}$,

\noindent{\rm (b)} $\min\,B_n=A_{n+1}$. (Arima sequence; see~{\em \cite{hinz-2017}} and cf.~\seqnum{A005578} in the {\rm OEIS}.
Recall that $\frac{A_{n+1}}{2^n}\rightarrow \frac{1}{3}$ as $n\rightarrow \infty$; cf.~{\em \cite[p.~7]{hinz-2017}}.)

\noindent{\rm (c)} If the sequence $b\in \mathbb{N}^{\mathbb{N}}$ is given by 
$$
b_1=1,\;\forall\,n\in\mathbb{N}_0\;\forall\,k\in [F_{n+2}]_0:b_{F_{n+3}+k}=b_{F_{n+1}+k}+2^{n},
$$
then $B=b(\mathbb{N})$. 
(This corresponds to sequence \seqnum{A052499} of the {\rm OEIS}: $b_n=\seqnum{A052499}(n-1)$.)
\end{proposition}
\begin{proof}
Statement (a) follows by induction from \eqref{eqn:Bn}. Similarly, the recurrence for $\min\,B_n$ in (b) is
$$
\min\,B_1=1,\;\min\,B_2=2,\;\forall\,n\in\mathbb{N}:\min\,B_{n+2}= 2^n+\min\,B_n,
$$
a recurrence also fulfilled by the Arima numbers $A_{n+1}$; cf.~\cite[p.~7]{hinz-2017}.

For (c) we can show by induction and making use of \eqref{eqn:Bn} that
$$
\forall\,n\in\mathbb{N}_0:B_n=\left\{b_k\ |\ k\in [F_{n+2}]_0\setminus [F_{n+1}]_0\right\}.
$$
As $\mathbb{N}=\Dst{\dot{\bigcup_{n\in\mathbb{N}_{(0)}}} [F_{n+2}]_0\setminus [F_{n+1}]_0}$, the elements of sequence $b$ 
exhaust the whole set $B$.
\end{proof}

\begin{remark}
The maximum distance from $\widehat{0}$ among 2-key vertices in $\ST_p^n$, $n\in\mathbb{N}$, is attained for $s=\widehat{0j}$, $j\in [p-2]$, and $s\in 0[p-2]^\nu\widehat{ij}$, $\{i.j\}\in {[p-2]\choose 2}$, $\nu\in [n-1]_0$. The minimum is taken in vertices $s=\left(0(p-1)\right)^{\lfloor (n-1)/2 \rfloor}\widehat{0j}$, $j\in [p-2]$ and in addition, if $n$ is even, in vertices $s=\left(0(p-1)\right)^{(n-2)/2}0\widehat{ij}$, $\{i,j\}\in {[p-2]\choose 2}$. \qed
\end{remark}

If we compare \eqref{eqn:Bn} with the recurrence for the sequence $c$, we see that $2b_n=c_n+1$, i.e., $2\cdot \seqnum{A052499}(n-1)=2\cdot \seqnum{A003754}(n)+2$, whence $\seqnum{A052499}(n-1)=\seqnum{A003754}(n)+1$ for $n\in\mathbb{N}$ (cf.~\cite[Corollary~1]{allouche-2005}).

The recurrence in \eqref{eqn:Bn} shows that the sequence $B$ does not depend on $p$, so we may assume that $p=3$, i.e., $D_1=\emptyset$. Then
another consequence of equations \eqref{eqn:Dn} and \eqref{eqn:Bn} is the following.

\begin{proposition}\label{prop:DandB}
Let $n\in\mathbb{N}_0$. Then $D_{n+1}=4B_n-1$ and 
$B_{n+2}=2B_{n+1}\,\dot\cup\,(4B_n-1)$.
\end{proposition}

\begin{proof}
For $n=0$ we have $D_1=\emptyset=4B_0-1$. For $n=1$ we get $D_2=\{3\}=4\{1\}-1=4B_1-1$. Now for $n\in\mathbb{N}_0$:
\begin{eqnarray*}
D_{n+3} &amp; = &amp; 2^{n+2}+D_{n+2}\cup D_{n+1}\\
&amp; = &amp; 2^{n+2}+ (4B_{n+1}-1)\cup (4B_n-1)\\
&amp; = &amp; 2^{n+2}+ 4(B_{n+1}\cup B_n)-1\\
&amp; = &amp; 4(2^n+B_{n+1}\cup B_n)-1\\
&amp; = &amp; 4B_{n+2}-1.
\end{eqnarray*}
The second statement then follows by \eqref{eqn:Brecurrence}. The union is disjoint for parity reasons.
\end{proof}

 From Proposition~\ref{prop:DandB} it follows that $B=\{1\}\cup 2B \cup (4B-1)$ (disjoint unions), so that $B$ fulfills the definition given in \cite[p.~2]{allouche-2005} and 
which is assumed to characterize the sequence \seqnum{A052499}, albeit with offset 0, in the OEIS. It is, however, not stated in literature, why the set $B\subset \mathbb{N}$ should be determined uniquely by the above condition. 
It is an example of a self-generating set; cf.~Lemma~\ref{lem:selfgen}. 


\subsection{The case $m=3$}\label{sec:STm3}

Primitive vertices cannot be 3-key vertices in $\ST_p^n$, which are therefore the elements of $\Dst{\widehat{\Psi}_n}:=\bigcup_{\nu=1}^n{_3\widehat{\Phi}_{p,\nu}}$, where for $n\in\mathbb{N}$:
$$
_3\widehat{\Phi}_{p,n}=\Big\{s\widehat{ij}\ |\ s=s_n\ldots s_2\in P^{n-1},\;\{i.j\}\in\textstyle{{P\choose 2}};\;
\dd^{(n)}(s\widehat{ij},\widehat{p-1})=3\cdot\dd^{(n)}(s\widehat{ij},\widehat{0})\Big\}.
$$
A vertex $s\widehat{ij}$ lies in $_3\widehat{\Phi}_{p,n}$, iff
\begin{equation}\label{eqn:misthree1hat}
(i\neq p-1\neq j)+\sum_{d=2}^n (s_d\neq p-1)\cdot 2^{d-1}=2+3(i\neq 0\neq j)+3\sum_{d=2}^n (s_d\neq 0)\cdot 2^{d-1}.
\end{equation}
If $n=1$, then $\LHS\leq 1&lt;2\leq \RHS$, so $_3\widehat{\Phi}_{p,1}=\emptyset=\widehat{\Psi}_1$. So let $n\geq 2$ and assume that $s_n\neq 0$. Then $\RHS\geq 2+3\cdot 2^{n-1}&gt;2^n-1\geq \LHS$, a contradiction. Therefore, $s_n=0$ and \eqref{eqn:misthree1hat} becomes
\begin{equation}\label{eqn:misthree2hat}
(i\neq p-1\neq j)+\sum_{d=2}^{n-1} (s_d\neq p-1)\cdot 2^{d-1}+2^{n-1}
=2+3(i\neq 0\neq j)+3\sum_{d=2}^{n-1} (s_d\neq 0)\cdot 2^{d-1}.
\end{equation}
If $n=2$, then necessarily $(i\neq p-1\neq j)=0=(i\neq 0\neq j)$, whence $_3\widehat{\Phi}_{p,2}=\{0\widehat{0(p-1)}\}=\widehat{\Psi}_2$. Let $n\geq 3$ and assume that $s_{n-1}=0$. Then $\RHS\leq 2+3M_{n-2}=2^{n-1}+2^{n-2}-1&lt;2^{n-1}+2^{n-2}\leq \LHS$, a contradiction. Similarly, if $s_{n-1}=p-1$, then $\LHS\leq M_{n-2}+2^{n-1}=3\cdot 2^{n-2}-1&lt;2+3\cdot 2^{n-2}\leq \RHS$; again a contradiction. It follows that $s_{n-1}\in [p-2]$ and \eqref{eqn:misthree2hat} becomes
\begin{equation}\label{eqn:misthree3hat}
(i\neq p-1\neq j)+\sum_{d=2}^{n-2} (s_d\neq p-1)\cdot 2^{d-1}=2+3(i\neq 0\neq j)+3\sum_{d=2}^{n-2} (s_d\neq 0)\cdot 2^{d-1}.
\end{equation}
We notice that \eqref{eqn:misthree3hat} is the same as \eqref{eqn:misthree1hat}, but with $n$ replaced by $n-2$. It follows that
$_3\widehat{\Phi}_{p,n}=\emptyset$, if $n$ is odd, and
$
_3\widehat{\Phi}_{p,n}=(0[p-2])^{(n-2)/2}0\widehat{0(p-1)},
$
if $n$ is even. In the latter case, 
$\dd^{(n)}(s\widehat{ij},\widehat{p-1})=M_n$ for $s\widehat{ij}\in{_3\widehat{\Phi}_{p,n}}$.

We can summarize the case $m=3$ in the following theorem.
\begin{theorem}\label{thm:mis3hat}
The set of $3$-key vertices in $\ST_p^n$ is 
$$
\widehat{\Psi}_n=\bigcup_{\mu=0}^{\lfloor n/2\rfloor-1} (0[p-2])^\mu0\widehat{0(p-1)}
$$
with
\begin{displaymath}
|\widehat{\Psi}_n|=\sum_{\mu=0}^{\lfloor n/2 \rfloor-1} (p-2)^\mu
=\begin{cases}
\Dst{\left\lfloor n/2 \right\rfloor,} 
&amp; \text{if $p=3\,$;}\\
\Dst{\frac{(p-2)^{\lfloor n/2 \rfloor}-1}{p-3},} 
&amp; \text{if $p\neq 3\,$.}
                 \end{cases} 
\end{displaymath}
The set of 3-key distances from $\ST_p^n$ is $\widehat{B}_n:=\left\{\frac{1}{3}2^{n-\nu} M_\nu\ |\ \nu\in [n]\;{\rm even}\right\}$ with $|\widehat{B}_n|=\lfloor n/2 \rfloor$ (\seqnum{A004526}).
\end{theorem}

\begin{remark}
1. In our test case $\ST_3^5$ we have key vertices $0\widehat{02}$ and $010\widehat{02}$ with key distances 8 and 10, respectively (see Figure~\ref{m=1}).

2. Note that $\widehat{B}_0=\emptyset=\widehat{B}_1$ and that for $n\geq 2$ we have $\min\,\widehat{B}_n=2^{n-2}$ and $\max\,\widehat{B}_n=\ell_{n-1}$, the Lichtenberg numbers (\seqnum{A000975}). As $\ell_{n-1}&lt;2^{n-1}$, the sets $\widehat{B}_n$ are disjoint. The elements of $\widehat{B}_n$ can be written as $\frac{1}{3}2^{n-\nu} M_\nu=\frac{1}{3}(2^n-2^{n-\nu})=2^{n-\nu}\ell_{\nu-1}$ for even $\nu\in [n]$. The set of all 3-key distances is
\begin{equation}\label{eqn:3distances}
\widehat{B}:=\bigcup_{n=0}^\infty \widehat{B}_n=\{2^i\ell_{2j+1}\ |\ i,j\in\mathbb{N}_0\}=\{(1(01)^j0^i)_2\ |\ i,j\in\mathbb{N}_0\}.
\end{equation}
This set can be written as a sequence $\widehat{b}\in\mathbb{N}^\mathbb{N}$ in an interesting way. If we define $\widetilde{\Delta}_0=0=\widetilde{\Delta}_1$ and $\widetilde{\Delta}_{N+2}=\widetilde{\Delta}_{N}+N+1$ for $N\in\mathbb{N}_0$, i.e., 
$$
\widetilde{\Delta}_N=\sum_{n=0}^N \left\lfloor n/2 \right\rfloor=\left\lfloor N^2/4 \right\rfloor=\left\lfloor N/2 \right\rfloor\cdot\left\lceil N/2 \right\rceil=\textstyle{\frac{1}{4}}(N^2-N\mod 2)
$$
(see the many entries for \seqnum{A002620} in the OEIS and note that $\widetilde{\Delta}_{N+1}+\widetilde{\Delta}_{N}={N+1\choose 2}=\Delta_N$), every $n\in\mathbb{N}$ can be written uniquely as $n=\widetilde{\Delta}_{N-1}+\rho$ with $N=\left\lceil 2\sqrt{n}\,\right\rceil\geq 2$ and a $\rho\in\left[\left\lfloor N/2 \right\rfloor\right]$.
Then $\widehat{B}=\widehat{b}(\mathbb{N})$ for the sequence $\widehat{b}$ given by
$$
\widehat{b}(\widetilde{\Delta}_{N-1}+\rho)=\textstyle{\frac{1}{3}}(2^N-2^{N-2\rho})=2^{N-2\rho}\ell_{2\rho-1}=\left(1(01)^{\rho -1}0^{N-2\rho}\right)_2,
$$
i.e., with $i=N-2\rho$ and $j=\rho -1$ in \eqref{eqn:3distances}. (This sequence $\widehat{b}$ is \seqnum{A181666}.)
The bijection 
$$
\mathbb{N}\ni \widetilde{\Delta}_{N-1}+\rho \leftrightarrow (N-2\rho,\rho-1)\in \mathbb{N}_0^2
$$
is quite remarkable. 

$\widehat{B}$ is also the self-generating set (cf.~Lemma~\ref{lem:selfgen}) with seed~1 and engendered by the two generating functions given by $\mathbb{N}\ni k\mapsto 2k$ and $f(2^i(2h+1))=2^i(8h+5)$ for $i,h\in\mathbb{N}_0$; note that $f(2^i\ell_{2j+1})=2^i\ell_{2(j+1)+1}$, whence $f(\widehat{B})=\widehat{B}\setminus \{2^i\ |\ i\in\mathbb{N}_0\}$.
\qed
\end{remark}


\subsection{The case $m=4$}\label{sec:STm4}

Again, primitive vertices cannot be 4-key vertices in $\ST_p^n$, which are therefore the elements of $\Dst{\widehat{\Psi}_n}:=\bigcup_{\nu=1}^n{_4\widehat{\Phi}_{p,\nu}}$, where for $n\in\mathbb{N}$:
$$
_4\widehat{\Phi}_{p,n}=\Big\{s\widehat{ij}\ |\ s=s_n\ldots s_2\in P^{n-1},\;\{i.j\}\in\textstyle{{P\choose 2}};\;
\dd^{(n)}(s\widehat{ij},\widehat{p-1})=4\cdot\dd^{(n)}(s\widehat{ij},\widehat{0})\Big\}.
$$
A vertex $s\widehat{ij}$ lies in $_4\widehat{\Phi}_{p,n}$, iff
$$
(i\neq p-1\neq j)+\sum_{d=2}^n (s_d\neq p-1)\cdot 2^{d-1}=3+4(i\neq 0\neq j)+\sum_{d=2}^n (s_d\neq 0)\cdot 2^{d+1}.
$$
As the RHS is odd, we must have $i\neq p-1\neq j$ and
$$
\sum_{d=2}^n (s_d\neq p-1)\cdot 2^{d-1}=2+4(i\neq 0\neq j)+\sum_{d=2}^n (s_d\neq 0)\cdot 2^{d+1}.
$$
The case $n=1$ cannot be satisfied, so that $_4\widehat{\Phi}_{p,1}=\emptyset$ and $|_4\widehat{\Phi}_{p,1}|=0$. Let $n\geq 2$. Then $s_2\neq p-1$, whence
\begin{equation}\label{eqn:misfour1hat}
\sum_{d=3}^n (s_d\neq p-1)\cdot 2^{d-1}=4(i\neq 0\neq j)+\sum_{d=2}^{n} (s_d\neq 0)\cdot 2^{d+1}.
\end{equation}
For $n=2$ we necessarily have $i=0$ and $j\in [p-2]$ and $s_2=0$, so that $_4\widehat{\Phi}_{p,2}=0\widehat{0[p-2]}$ and $|_4\widehat{\Phi}_{p,2}|=p-2$; key distance is $\dd^{(2)}(0\widehat{0j},\widehat{0})=1$.
For $n\geq 3$ we get $s_{n-1}=0=s_n$, which for $n=3$ means $\{i,j\}\in {[p-2]\choose 2}$, $s_2=0=s_3$, whence $_4\widehat{\Phi}_{p,3}=\left\{00\widehat{ij}\ |\ \{i,j\}\in {[p-2]\choose 2}\right\}$ and $|_4\widehat{\Phi}_{p,3}|={p-2\choose 2}$; key distance is $\dd^{(3)}(00\widehat{ij},\widehat{0})=2$. For $n=4$ we get $i\neq 0\neq j$, $s_2\in [p-2]$, and $s_3=0=s_4$, i.e., $_4\widehat{\Phi}_{p,4}=\left\{00s_2\widehat{ij}\ |\ s_2\in [p-2],\;\{i,j\}\in {[p-2]\choose 2}\right\}$ and $|_4\widehat{\Phi}_{p,4}|=(p-2){p-2\choose 2}$; key distance is $\dd^{(4)}(00s_2\widehat{ij},\widehat{0})=4$. For $n\geq 5$ we deduce from \eqref{eqn:misfour1hat} that, in addition to the conditions already fixed,  $s_3=p-1\Leftrightarrow \widehat{ij}\in\widehat{0[p-2]}$, $\forall\,d\in [n-2]\setminus [3]:s_d=p-1\Leftrightarrow s_{d-2}=0$ and $s_{n-3}\neq 0\neq s_{n-2}$. This leads to the following recurrence relation for $n\in\mathbb{N}_0$.
$$
_4\widehat{\Phi}_{p,4+n}=00[p-2]_4\widehat{\Phi}_{p,3+n}^{\prime\prime}\;\cupdot\;00(p-1)[p-2]_4\widehat{\Phi}_{p,1+n}^\prime\:\cupdot\;00(p-1)(p-1)_4\widehat{\Phi}_{p,n},
$$
where each prime indicates the deletion of a leading 0; e.g., $_4\widehat{\Phi}_{p,2}^\prime= \widehat{0[p-2]}$. This means that
$$
|_4\widehat{\Phi}_{p,4+n}|=(p-2)|_4\widehat{\Phi}_{p,3+n}|+(p-2)|_4\widehat{\Phi}_{p,1+n}|+|_4\widehat{\Phi}_{p,n}|.
$$
If for $q\in\mathbb{N}_0$ we define the sequences $(\widetilde{FF}_{q,n})_{n\in\mathbb{N}_0}$ by
$$
\widetilde{FF}_{q,0}\,=\,0\,=\,\widetilde{FF}_{q,1},\;\widetilde{FF}_{q,2}\,=\,q,\;\widetilde{FF}_{q,3}\,=\,\textstyle{{q\choose 2}},
$$
$$
\widetilde{FF}_{q,n+4}\,=q(\widetilde{FF}_{q,n+3}+\widetilde{FF}_{q,n+1})+\widetilde{FF}_{q,n},
$$
we get
\begin{theorem}\label{thm:st4}
If $p\in\mathbb{N}$, $p\geq 2$, and $n\in\mathbb{N}_0$, then
$|_4\widehat{\Phi}_{p,n}| = \widetilde{FF}_{p-2,n}.$
\end{theorem}

For $q=0$ we have $\widetilde{FF}_{0,n}=0$, which reflects the fact that 5 does not divide $2^n$. For $q=1$ the sequence is $\widetilde{FF}_{1,n}=\overline{FF}_{n+1}$. The sequence of partial sums is $|_4\widehat{\Psi}_{3,n}|=FF_{n+1}$. In our standard example, the graph $\ST_3^5$, we therefore have two 4-key vertices, namely $0\widehat{01}$ and $0021\widehat{01}$ with 4-key distances 8 and 7, respectively (see Figure~\ref{m=1}). The sequence 
$$\widetilde{FF}_{2,n}=\textstyle{\frac{1}{8}}\left((5-3\sqrt{2})(1+\sqrt{2})^n+(5+3\sqrt{2})(1-\sqrt{2})^n+x_n\right),
$$
where $x_n=-10,\,2,\,10,\,-2$, if $n\bmod 4=0,\,1,\,2,\,3$, respectively,
starts $$0,0,2,1,2,8,20,45,108,264,638,1537,\ldots;$$ this is \seqnum{A353581} in the OEIS. Its partial sums form sequence \seqnum{A353582}, namely
\begin{eqnarray*}
|_4\widehat{\Psi}_{4,n}| &amp; = &amp; \textstyle{\frac{1}{16}}\left((4-\sqrt{2})(1+\sqrt{2})^n+(4+\sqrt{2})(1-\sqrt{2})^n+y_n\right)\\
&amp; = &amp; 0,0,2,3,5,13,33,78,186,450,1088,2625,\ldots
\end{eqnarray*}
with $y_n=-8,\,-4,\,16,\,12$, if $n\bmod 4=0,\,1,\,2,\,3$, respectively.

For the sets of 4-key distances in $\ST_p^n$, $p\geq 3$, we get the recurrence
$$
\widehat{DD}_0=\emptyset=\widehat{DD}_1,\;\widehat{DD}_2=\{1\},\;\widehat{DD}_3=\{2\},
$$
$$
\widehat{DD}_{n+4}=2^{n+1}+\left(\widehat{DD}_{n+3}\cup\left(2^n+\left(\widehat{DD}_{n+1}\cup \widehat{DD}_n\right)\right)\right).
$$
For $n\geq 2$ we have $\max \widehat{DD}_n=2^{n-2}$ and
\begin{displaymath}
  \min \widehat{DD}_n =\begin{cases}
                  \frac{1}{5}(2^n+4), &amp; \text{if $n\mod 4=0\,$;}\\
                  \frac{1}{5}(2^n+3), &amp; \text{if $n\mod 4=1\,$;}\\
                  \frac{1}{5}(2^n+1), &amp; \text{if $n\mod 4=2\,$;}\\
                  \frac{1}{5}(2^n+2), &amp; \text{if $n\mod 4=3\,$.}
                 \end{cases}
\end{displaymath}
Asymptotically, for large $n$, we have $\min \widehat{DD}_n \sim \frac{1}{5}2^n$ and $\max \widehat{DD}_n \sim \frac{1}{4}2^n$.

 The sequence $\widehat{cc}$ obtained from the union over $n\in\mathbb{N}$ of the sets $\widehat{DD}_n$ by order of size is given by $\widehat{cc}(1)=1$ and $\forall\,n\in\mathbb{N}_0$:
\begin{eqnarray*}
\forall\,k\in [FF_n+FF_{n+1}]: &amp; \widehat{cc}(\Sigma FF_{n+3}+k)=3\cdot 2^{n-1}+\widehat{cc}(\Sigma FF_{n-1}+k),\\
\forall\,k\in [FF_{n+3}]: &amp; \widehat{cc}(\Sigma FF_{n+4}-FF_{n+3}+k)=2^{n}+\widehat{cc}(\Sigma FF_{n+2}+k).
\end{eqnarray*}
The sequence $\widehat{cc}$ (with offset 1) starts $$1,2,4,7,8,13,14,15,16,26,28,29,30,31,32,\ldots$$ and is \seqnum{A353579} in the  OEIS. It can be viewed as the self-generating sequence with seed~1 and generating function set $\{k\mapsto 2^n+k,k\mapsto 3\cdot 2^{n+1}+k,k\mapsto 3\cdot 2^{n+2}+k\}$, where $n$ is the smallest non-negative integer such that $k\leq 2^n$ (cf.~Lemma~\ref{lem:selfgen}).

\section{Outlook}\label{sec:outlook}

For fixed $m$ and $p$, the string sets of $m$-key vertices, $_m\Psi_{p,n}$ for Sierpi\'{n}ski graphs $S_p^n$ and $_m\widehat{\Psi}_{p,n}$ for Sierpi\'{n}ski triangle graphs $\ST_p^n$, are often, perhaps always, regular languages,
denoted by regular expressions.  For example, the language of non-empty strings in $_2\Psi_{3,n}$ can be
represented by the regular expression
$$
0(1 \vee 20)^{\star}2,
$$
illustrating equation (\ref{eqn:srecurrence}) in the proof of Theorem
\ref{thm:paulsgem}. This regular expression denotes the language of all strings that begin with
the character 0 and end with the character 2, with zero or more substrings,
each either 1 or 20, in between;
the star
character stands for the star closure, or Kleene closure, of a language.
If we wish to include the empty
string, which is the only key vertex when $n=0$, we can use the more compact but
perhaps less intuitive regular expression
$$
(01^{\star}2)^{\star}.
$$
  From this, all distance properties can be deduced via the formulas 
\eqref{eqn:distextreme} and \eqref{eqn:distprimitive}, \eqref{eqn:dist}, respectively. 
The counting sequences $|_{2^k}\Psi_{p,n}|$ for $m$-key vertices when $m=2^k$ appear to have
interesting forms, extending the formulas for $k\in \{0,1,2\}$ presented
here. Moreover, it will be interesting to investigate the fractal structures
engendered by the underlying sets of key vertices.

\section{Acknowledgments}\label{sec:acknowledge} We thank Sandi Klav\v{z}ar (Ljubljana) for a valuable discussion. We are grateful for the very thoughtful remarks and suggestions made by an anonymous referee.

 
\begin{sidewaystable}[htb]
 \begin{center}
 \begin{tabular}{|c|c||r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}
 \hline 
 &amp; &amp; \multicolumn{18}{c|}{initial entries for $n=$} \\
 sequence &amp; OEIS$^{\textregistered}$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 &amp; 15 &amp; 16 &amp; 17 \\
 \hline\hline
$F$ &amp; \seqnum{A000045} &amp; 0 &amp; 1 &amp; 1 &amp; 2 &amp; 3 &amp; 5 &amp; 8 &amp; 13 &amp; 21 &amp; 34 &amp; 55 &amp; 89 &amp; 144 &amp; 233 &amp; 377 &amp; 610 &amp; 987 &amp; 1597 \\
\hline
$\overline{FF}$ &amp; (\seqnum{A070550}) &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 2 &amp; 3 &amp; 6 &amp; 10 &amp; 15 &amp; 24 &amp; 40 &amp; 65 &amp; 104 &amp; 168 \\
\hline
$FF$ &amp; (\seqnum{A006498}) &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 2 &amp; 4 &amp; 6 &amp; 9 &amp; 15 &amp; 25 &amp; 40 &amp; 64 &amp; 104 &amp; 169 &amp; 273 &amp; 441 \\
\hline
$\Sigma FF$ &amp; (\seqnum{A097083})? &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 5 &amp; 9 &amp; 15 &amp; 24 &amp; 39 &amp; 64 &amp; 104 &amp; 168 &amp; 272 &amp; 441 &amp; 714 &amp; 1155 \\
\hline \hline
$a$ &amp; (\seqnum{A003754}) &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 5 &amp; 6 &amp; 7 &amp; 10 &amp; 11 &amp; 13 &amp; 14 &amp; 15 &amp; 21 &amp; 22 &amp; 23 &amp; 26 &amp; 27 &amp; 29 \\
\hline
$b$ &amp; (\seqnum{A052499}) &amp;  &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 6 &amp; 7 &amp; 8 &amp; 11 &amp; 12 &amp; 14 &amp; 15 &amp; 16 &amp; 22 &amp; 23 &amp; 24 &amp; 27 &amp; 28 \\
\hline
$\widehat{b}$ &amp; \seqnum{A181666} &amp; &amp; 
1 &amp; 2 &amp;  4 &amp;  5 &amp;  8 &amp;  10 &amp;  16 &amp;  20 &amp;  21 &amp;  32 &amp;  40 &amp;  42 &amp;  64 &amp;  80 &amp;  84 &amp;  85 &amp;  128 \\
\hline
$c$ &amp; \seqnum{A247648} &amp; 0 &amp; 1 &amp; 3 &amp; 5 &amp; 7 &amp; 11 &amp; 13 &amp; 15 &amp; 21 &amp; 23 &amp; 27 &amp; 29 &amp; 31 &amp; 43 &amp; 45 &amp; 47 &amp; 53 &amp; 55 \\
\hline
$cc$ &amp; \seqnum{A353578}  &amp;  &amp; 3 &amp; 7 &amp; 15 &amp; 27 &amp; 31 &amp; 51 &amp; 55 &amp; 59 &amp; 63 &amp; 103 &amp; 111 &amp; 115 &amp; 119 &amp; 123 &amp; 127 &amp; 207 &amp; 219 \\
\hline
$\widehat{cc}$ &amp; \seqnum{A353579} &amp; &amp; 1 &amp; 2 &amp; 4 &amp; 7 &amp; 8 &amp; 13 &amp; 14 &amp; 15 &amp; 16 &amp; 26 &amp; 28 &amp; 29 &amp; 30 &amp; 31 &amp; 32 &amp; 52 &amp; 55\\
\hline
 \end{tabular}
 \end{center}
 \caption{Some integer sequences addressed in the text (An OEIS entry in brackets means that the offset is shifted.)}
 \label{tab:sequences}
\end{sidewaystable}

\begin{thebibliography}{99}

\bibitem{allouche-2005}
J.-P.~Allouche, J.~Shallit, and G.~Skordev,
Self-generating sets, integers with missing blocks, and substitutions, 
{\it Discrete Math.} {\bf 292} (2005), 1--15.

\bibitem{benjamin-2003}
A.~T.~Benjamin and J.~J.~Quinn, 
{\it Proofs That Really Count},
The Mathematical Association of America, 2003.

\bibitem{falcon-2007}
S.~Falc\'{o}n and \'{A}.~Plaza, On the Fibonacci $k$-numbers,
{\it Chaos Solitons Fractals} {\bf 32} (2007), 1615--1624.

\bibitem{grubb-2021}
T.~Grubb and C.~Wolird, 
Cyclotomic points and algebraic properties of polygon diagonals,
{\it Integers} {\bf 21} (2021), A40.

\bibitem{hinz-2017}
A.~M.~Hinz, The Lichtenberg sequence, {\it Fibonacci Quart.} {\bf 55}
(2017), 2--12.

\bibitem{hinz-2014}
A.~M.~Hinz and C.~Holz auf der Heide, An efficient algorithm to determine
all shortest paths in Sierpi\'{n}ski graphs, {\it Discrete Appl.\ Math.}
{\bf 177} (2014), 111--120.

\bibitem{hinz-2020}
A.~M.~Hinz, C.~Holz auf der Heide, and S.~S.~Zemlji\v{c}, Metric properties of Sierpi\'{n}ski triangle graphs, {\it Discrete Appl.\ Math.}, in press.

\bibitem{hinz-2013}
A.~M.~Hinz, S.~Klav\v{z}ar, and C.~Petr, {\it The Tower of Hanoi---Myths and Maths}, Second Edition, Springer, 2018.

\bibitem{hinz-2016}
A.~M.~Hinz, S.~Klav\v{z}ar, and S.~S.~Zemlji\v{c}, A survey and classification of
Sierpi\'{n}ski-type graphs, {\it Discrete Appl.\ Math.} {\bf 217} (2017), 565--600.

\bibitem{hinz-1990}
A.~M.~Hinz and A.~Schief, The average distance on the Sierpi\'{n}ski gasket,
{\it Probab. Theory Related Fields} {\bf 87} (1990), 129--138.

\bibitem{hinz-2019}
A.~M.~Hinz and P.~K.~Stockmeyer, Discovering Fibonacci numbers, Fibonacci
words, and a Fibonacci fractal in the Tower of Hanoi, in
K. Dilcher, ed., {\it Proc. 18th Int'l Conf. on Fibonacci
Numbers and Their Applications}, in {\it Fibonacci
Quart.}  {\bf 57} (5) (2019), 72--83.

\bibitem{lucas-1878}
E.~Lucas, Th\'{e}orie des fonctions num\'{e}riques simplement p\'{e}riodiques, {\it Amer. J. Math.} {\bf 1} (1878), 184--240, 289--321.

\bibitem{paul-2017}
P.~K.~Stockmeyer, An exploration of sequence \seqnum{A000975},
in C. Ballot, P. G. Anderson, and T. Komatsu, eds.,
{\it Proc. 17th Int'l Conf. on Fibonacci Numbers and
Their Applications}, in
{\it Fibonacci Quart.}  {\bf 55} (5) (2017), 174--185.


\end{thebibliography}

\bigskip
\hrule
\bigskip
	
\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05C12; Secondary 11B39, 68R15.

\noindent \emph{Keywords:} self-generating set, Sierpi\'{n}ski graph, Sierpi\'{n}ski triangle graph, distance in graphs, integer sequence, Fibonacci number, Pell number.

\bigskip \hrule \bigskip

\noindent (Concerned with sequences 
\seqnum{A000045},
\seqnum{A000129},
\seqnum{A000225},
\seqnum{A000975},
\seqnum{A001045},
\seqnum{A002450},\hfill\\
\seqnum{A002620},
\seqnum{A003754},
\seqnum{A004526},
\seqnum{A005578},
\seqnum{A006498},
\seqnum{A023758},
\seqnum{A048654},
\seqnum{A052499},
\seqnum{A070550},
\seqnum{A089928},
\seqnum{A089931},
\seqnum{A097083},
\seqnum{A181666},
\seqnum{A182512},
\seqnum{A247648},
\seqnum{A353578},
\seqnum{A353579},
\seqnum{A353580},
\seqnum{A353581}, and
\seqnum{A353582}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 9 2022;
revised versions received  May 13 2022; June 9 2022.
Published in {\it Journal of Integer Sequences}, June 10 2022.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>