#A111 INTEGERS 25 (2025)
A MULTIGRAPH CHARACTERIZATION OF PERMUTIPLE
STRINGS
Benjamin V. Hol
Depa men o Ma hema ics, Sou hwes e n O egon Communi y College, O egon
[email p o ec ed]
Recei ed: 5/11/25, Accep ed: 11/14/25, Published: 11/25/25
Abs ac
A pe mu iple is a na u al numbe whose ep esen a ion in some base is an in ege
mul iple o a numbe whose ep esen a ion has he same collec ion o digi s. A
p e ious pape u ilizes a ini e-s a e-machine cons uc ion and i s s a e g aph o
ecognize pe mu iples and o gene a e new examples. Pe mu iples a e associa ed
wi h walks on he s a e g aph which necessa ily sa is y ce ain condi ions. Howe e ,
he abo e e o does no p o ide su icien condi ions o he exis ence o pe mu-
iples. In his pape , we p o ide such a condi ion which we will s a e using he
language o mul ig aphs.
1. In oduc ion
Le b > 1 be an in ege . A pe mu iple is a na u al numbe which is an in ege
mul iple o some pe mu a ion o i s digi s in base b[8]. Speci ic cases o digi -
pe mu a ion p oblems include cyclic pe mu a ions o digi s [4, 12], o example,
714285 = 5 ·142857,as well as digi e e sals [5, 6, 7, 13, 16, 18, 19, 20], which
include 87912 = 4 ·21978 and 98901 = 9 ·10989.Numbe s which a e mul iples o
cyclic pe mu a ions o hei digi s a e known as cyclic numbe s [4]. Numbe s which
a e mul iples o hei e e sals a e known by se e al names, including palin iples
[5, 6, 7], e e se mul iples [13, 16, 19, 20], and e e se di iso s [18].
Ano he speci ic case o pe mu iples wo h men ioning is a pape by Qu and
Cu an [14] which conside s base-bnumbe s which a e mul iples o (bb−1−1)/(b−1)2,
whose ep esen a ion is all consecu i e base-bdigi s 1 h ough b−1.Two base-10
examples include 987654312 = 8 ·123456789 and 493827156 = 4 ·123456789.
Some wo ks place no es ic ions on he ype o pe mu a ion which may a ise in
an a bi a y base and mul iplie [8, 9, 10, 11]. In [8, 9], he au ho desc ibes me hods
o inding new examples o pe mu iples om he digi s o known examples. Fo
ins ance, using hese me hods, we a e able o ind new examples 79128 = 4 ·19782
DOI: 10.5281/zenodo.17711714
INTEGERS: 25 (2025) 2
and 78912 = 4 ·19728 om he known example men ioned abo e, 87912 = 4 ·
21978. O he wo ks by he au ho [10, 11] u ilize g aph- heo e ical and ini e-
s a e-machine me hods o p oduce examples wi h any sui able numbe o digi s.
These me hods a e modi ica ions o he wo k o Hoey [5] and Sloane [16], and bo h
apply wha a e ul ima ely simila echniques o he digi - e e sal p oblem. The
o me uses ini e-s a e-machine me hods, while he la e uses a g aph- heo e ical
app oach. Ano he example o applying ini e-s a e-machine echniques o base-
dependen in ege sequences is a pape by Fabe and G an ham [2] which inds
pai s o in ege s whose sum is he e e se o hei p oduc . Fo example, 3 and 24
ha e his p ope y since 3 + 24 = 27 and 3 ·24 = 72.
The me hods de eloped in [10] use a ini e-s a e-machine cons uc ion, known
as he Hoey-Sloane machine, and i s s a e g aph, known as he Hoey-Sloane g aph,
which desc ibes a collec ion o possible base-bmul iplica ions by a single-digi mul-
iplie n. The s a es o he Hoey-Sloane machine a e he possible ca ies which
may occu when pe o ming digi -p ese ing mul iplica ion, and he inpu alphabe
consis s o o de ed pai s ep esen ing di ec ed edges om he mo he g aph, which
ca alogs how digi s may be pe mu ed in a single-digi mul iplica ion. The ini ial
s a e o he machine mus be ze o since he ca y co esponding o he i s digi in
any single-digi mul iplica ion is de ined o be ze o [8]. Simila ly, he e minal digi
o a mul iplica ion equi es he inal (accep ing) s a e o be ze o, o he wise he e
would be digi s beyond he e minal digi . I is shown in [10] ha inpu s ings
which ep esen pe mu iples, known as pe mu iple s ings, consis o o de ed pai s
which make up cycles on he mo he g aph. In his con ex , pe mu iples co espond
o a sequence o s a e ansi ions (walks on he Hoey-Sloane g aph) beginning and
ending wi h he ze o s a e, whe e each ansi ion is induced by a collec ion o edges
which is a mul ise union o cycles o he mo he g aph.
In his pape , we con inue he wo k desc ibed abo e o es ablish su icien condi-
ions o he exis ence o pe mu iple s ings, yielding a mul ig aph cha ac e iza ion
o pe mu iple s ings. We also apply he esul s o se e al examples, which desc ibe
how o c ea e no el pe mu iple examples o any sui able leng h.
2. Summa y o P e ious Wo k
Wha ollows is a summa y o se e al esul s and de ni ions om p e ious wo ks
[8, 10] ha we will use in his a icle.
2.1. Basic De ini ions and Resul s
The no a ion (dk, dk−1, . . . , d0)bis used o ep esen Pk
j=0 djbj,whe e 0 ≤dj< b
o all 0 ≤j≤k. We may now de ine wha i means o be a pe mu iple numbe .
INTEGERS: 25 (2025) 3
De ini ion 1 ([8]).Le 1 < n < b be a na u al numbe , and le σbe a pe mu a ion
on {0,1,2,...,k}. We say ha (dk, dk−1, . . . , d0)bis an (n, b, σ)-pe mu iple p o ided
(dk, dk−1, . . . , d1, d0)b=n(dσ(k), dσ(k−1), . . . , dσ(1), dσ(0))b.
When σi sel is no impo an o he discussion, we will e e o (dk, dk−1, . . . , d0)b
as simply an (n, b)-pe mu iple. The collec ion o all base-bpe mu iples ha ing
mul iplie nwill be e e ed o as (n, b)-pe mu iples.
The nex esul ela es he digi s and ca ies o a pe mu iple.
Theo em 1 ([8]).Le (dk, dk−1, . . . , d0)bbe an (n, b, σ)-pe mu iple, and le cjbe
he j hca y. Then,
bcj+1 −cj=ndσ(j)−dj
o all 0≤j≤k.
The ca ies in any pe mu iple mul iplica ion a e always less han he mul iplie .
Theo em 2 ([8]).Le (dk, dk−1, . . . , d0)bbe an (n, b, σ)-pe mu iple, and le cjbe
he j h ca y. Then, cj≤n−1 o all 0≤j≤k.
2.2. Pe mu iple G aphs and he Mo he G aph
Fo any pe mu iple, we may de ine a di ec ed g aph which desc ibes he mos es-
sen ial p ope ies o he digi pe mu a ion.
De ini ion 2 ([10]).Le p= (dk, dk−1, . . . , d0)bbe an (n, b, σ)-pe mu iple. We
de ine a di ec ed g aph, called he g aph o p, deno ed by Gp, o consis o he
collec ion o base-bdigi s as e ices, and he collec ion o di ec ed edges Ep=
dj, dσ(j)|0≤j≤k.A g aph G o which he e is a pe mu iple psuch ha
G=Gpis called a pe mu iple g aph.
Fo he emainde o his pape , we may d op he “di ec ed” e minology wi h he
unde s anding ha all g aphs and mul ig aphs conside ed he e will ha e di ec ed
edges.
Table 1 gi es a collec ion o pe mu iples wi h he same g aph. Thei common
g aph is shown in Figu e 1.
(4,10, σ)-Pe mu iple σ
(8,7,9,1,2)10 = 4 ·(2,1,9,7,8)10 ρ
(8,7,1,9,2)10 = 4 ·(2,1,7,9,8)10 (1,2)ρ(1,2)
(7,9,1,2,8)10 = 4 ·(1,9,7,8,2)10 ψ−4ρψ4
(7,1,9,2,8)10 = 4 ·(1,7,9,8,2)10 ψ−4(1,2)ρ(1,2)ψ4
Table 1: Pe mu iples wi h he same g aph as (8,7,9,1,2)10 = 4 ·(2,1,9,7,8)10,
whe e ψ= (0,1,2,3,4) and ρis he e e sal pe mu a ion.
INTEGERS: 25 (2025) 4
0
1
23
4
5
6
7 8
9
Figu e 1: The di ec ed g aph which esul s om aking he collec ion o o de ed
pai s dj, dσ(j)|0≤j≤4 om any example in Table 1 as edges.
Pe mu iple g aphs p o ide a amewo k o classi ying pe mu iples.
De ini ion 3 ([10]).Le pbe an (n, b)-pe mu iple wi h g aph Gp.We de ine he
class o p o be he collec ion Co all (n, b)-pe mu iples qsuch ha Gqis a subg aph
o Gp.We also de ine he g aph o he class o be Gp,which we will deno e as GC
and will call he g aph o C.
Fo an (n, b)-pe mu iple (dk, . . . , d0)b=n(dσ(k), .. . , dσ(0))bi is shown in [10]
ha λ(dj+ (b−n)dσ(j))≤n−1 o all 0 ≤j≤k, whe e λgi es he leas non-
nega i e esidue modulo b. This condi ion pu s a es ic ion on he possible edges
o a pe mu iple g aph, and we s a e i as a heo em.
Theo em 3 ([10]).Le p= (dk, dk−1, . . . , d0)bbe an (n, b, σ)-pe mu iple wi h g aph
Gp.Then, o any edge (dj, dσ(j))o Gp,i mus be ha λdj+ (b−n)dσ(j)≤n−1
o all 0≤j≤k, whe e λgi es he leas non-nega i e esidue modulo b.
Theo em 3 enables us o ga he all possible edges o a pe mu iple g aph in o a
single g aph o ob ain he mo he g aph.
De ini ion 4 ([10]).The (n, b)-mo he g aph, deno ed M, is he g aph ha ing
all base-bdigi s as i s e ices and he collec ion o edges (d1, d2) sa is ying he
inequali y λ(d1+ (b−n)d2)≤n−1.
The nex esul unde pins he me hods p esen ed in [10].
Theo em 4 ([10]).Le Cbe any (n, b)-pe mu iple class. Then, GCis a union o
cycles o M.
We now p o ide he eade wi h an example which b ings oge he he concep s
we ha e co e ed so a .
INTEGERS: 25 (2025) 5
Example 1. The (4,10)-mo he g aph is displayed in Figu e 2. Le ing p=
(8,7,9,1,2)10 = 4 ·(2,1,9,7,8)10 om Table 1, and Cbe he (4,10)-pe mu iple
class wi h g aph GC=Gp,Figu e 2 ea u es he g aph o Cin bold ed.
0
1
23
4
5
6
7 8
9
Figu e 2: The (4,10)-mo he g aph wi h he g aph o C ea u ed in bold ed.
2.3. Fini e-S a e-Machine Desc ip ion o he Pe mu iple P oblem
Taking he ca ies o a pe mu iple as a collec ion o s a es, he abo e concep s can
be placed wi hin a ini e-s a e-machine amewo k. Taking non-nega i e in ege s
less han nas he collec ion o s a es, and he edges o Mas he inpu alphabe ,
he equa ion
c2= [nd2−d1+c1]÷b(1)
de ines a s a e- ansi ion unc ion om s a e c1 o s a e c2wi h (d1, d2) se ing as
he inpu which induces he ansi ion. This ansi ion co esponds o a labeled
edge on he s a e diag am as seen in Figu e 3.
c1c2
(d1, d2)
Figu e 3: An edge on he s a e diag am.
The i s ca y c0o any single-digi mul iplica ion is ze o by de ini ion [8]. This is
o say ha he ini ial s a e mus be ze o. Also, o an ℓ-digi (n, b)-pe mu iple, cℓ
mus also be ze o, o he wise, he esul would be an (ℓ+ 1)-digi numbe . Thus,
INTEGERS: 25 (2025) 6
he ze o s a e is he only possible accep ing s a e. The abo e is called he (n, b)-
Hoey-Sloane machine, and i s s a e diag am is called he (n, b)-Hoey-Sloane g aph,
which we deno e as Γ.
Digi pai s (d1, d2) which sol e Equa ion (1) o pa icula alues o c1and c2
a e no unique. Tha is, he e a e gene ally mul iple inpu s ha he machine will
ecognize o a ansi ion o occu . Thus, a collec ion o inpu s is assigned o each
edge on Γ by he mapping (c1, c2)7→ {(d1, d2)∈EM|c2= [nd2−d1+c1]÷b},
whe e EMis he collec ion o edges o M.
In he nex sec ion, we will de ine a labeled mul ig aph ep esen a ion o Γ,whe e
a unique mul i-edge is assigned o each inpu .
The language o inpu s ings accep ed by he (n, b)-Hoey-Sloane machine is
deno ed as L. Thus, Lmay be desc ibed as ini e sequences o edge-label inpu s
which de ine walks on Γ whose ini ial and inal s a es a e ze o. Such walks a e
called L-walks. Membe s o Lwhich p oduce pe mu iple numbe s a e called (n, b)-
pe mu iple s ings.
We may in e p e Theo em 4 anew in his se ing.
Co olla y 1 ([10]).Le s= (d0,ˆ
d0)(d1,ˆ
d1)···(dk,ˆ
dk)be a membe o L. I sis a
pe mu iple s ing, hen he collec ion o o de ed-pai inpu s o sis a union o cycles
o M.
Co olla y 1 ells us ha any pe mu iple s ing mus consis o a collec ion o
mo he -g aph edge inpu s which induce an L-walk on Γ and whose union is a col-
lec ion o cycles o M. We no e, howe e , ha sa is ying he abo e wo condi ions
is no su icien o a s ing o be a pe mu iple s ing. An example is p o ided by
[10] o a membe o Lwhose union is a collec ion o mo he -g aph cycles, ye is
no a pe mu iple s ing. A mo e p ecise desc ip ion o hese ideas equi es ha we
es a e some de ini ions om [10].
De ini ion 5 ([10]).Le C={C0, C1, . . . , Cm}be he cycles o M. Fo each elemen
Cjo C,de ine a subg aph Γjo Γ,whe e each edge o Γjis assigned he edge-label
collec ion by he mapping (c1, c2)7→ {(d1, d2)∈Cj|c2= [nd2−d1+c1]÷b}.Any
edge (c1, c2) o which his collec ion is emp y will no be included as an edge on
Γj.Wi h he abo e edges, any s a e o which bo h he indeg ee and ou deg ee a e
ze o will no be included as a e ex. Each Γjwill be e e ed o as he image o
Cj,o simply as a cycle image.
In wha ollows, we will dis inguish he usual se - heo e ic union ∪ om mul ise
unions by using he no a ion ⊎.Fo example, he mul ise union o he mul ise s
{1,2,2,3}and {2,3,4}is deno ed as {1,2,2,3} ⊎ {2,3,4}={1,2,2,2,3,3,4}.We
suppose ha Iis a mul ise whose suppo is a subse Jo {0,1, . . . , m}.Then, i
he cycle-image union ΓJ=Sj∈JΓj(edge labels included) is a s ongly-connec ed
subg aph o Γ con aining he ze o s a e, hen ΓJdesc ibes a machine which ecog-
nizes membe s o Lwhose inpu s o m he union o cycles Sj∈JCj.I he mul ise
INTEGERS: 25 (2025) 7
cycle union CI=Uj∈ICjcan be o de ed in o a s ing sbelonging o L, hen s
is a pe mu iple s ing. We no e ha e e y elemen o CImus be used, including
epea ed elemen s, o he wise, he mul ise s o le and igh componen s will no be
equal, esul ing in a mul iplica ion which does no p ese e he digi s.
We now p o ide he eade wi h ano he example by conside ing he (4,10)-
Hoey-Sloane g aph.
Example 2. The (4,10)-Hoey-Sloane g aph is shown in Figu e 4. The g aph depic -
ing he union o he images o he cycles o GC om Example 1 is shown in bold ed.
The cycles o GCa e C0={(9,9)}, C1={(2,8),(8,2)},and C2={(1,7),(7,1)},
and he cycle-image union may be mo e p ecisely deno ed as Γ0∪Γ1∪Γ2.
Using he Hoey-Sloane g aph, he mul ise union C0⊎C1⊎C1⊎C2⊎C2may be
o de ed in o a membe o L, o ming a pe mu iple s ing. The e a e mul iple ways o
accomplishing his, one o which is (8,2)(8,2)(2,8)(9,9)(1,7)(1,7)(7,1)(2,8)(7,1),
yielding a new (4,10)-pe mu iple (7,2,7,1,1,9,2,8,8)10 = 4·(1,8,1,7,7,9,8,2,2)10.
Ano he possible o de ing is (8,2)(2,8)(1,7)(7,1)(2,8)(9,9)(1,7)(7,1)(8,2),which
gi es he new example (8,7,1,9,2,7,1,2,8)10 = 4 ·(2,1,7,9,8,1,7,8,2)10.
As no ed in [11], no e e y mul ise union can be o de ed in o a pe mu iple s ing.
As a i ial example, any o he abo e cycles indi idually a e no su icien o o m
an elemen o L. A less i ial example is C1⊎C1⊎C2,which is also impossible o
o de in o a membe o L. We will add ess his speci ic case in a la e example.
Gene ally speaking, we see ha a s ongly-connec ed union o cycle images con-
aining he ze o s a e is a necessa y condi ion o o de ing i s co esponding mul ise
union o mo he -g aph cycles in o pe mu iple s ings [10], bu i is no a su icien
one. Finding su icien condi ions is he pu pose o his e o .
0
s a 1 2 3
(0,0),(4,1),(8,2)(3,3),(7,4) (2,5),(6,6) (1,7),(5,8),(9,9)
(2,3),(6,4)
(1,0),(5,1),(9,2) (0,2),(4,3),(8,4)
(1,5),(5,6),(9,7)
(3,8),(7,9)
(0,7),(4,8),(8,9)
(3,5),(7,6)
(1,2),(5,3),(9,4)
(0,5),(4,6),(8,7)
(2,8),(6,9)
(2,0),(6,1)
(3,0),(7,1)
Figu e 4: The (4,10)-Hoey-Sloane g aph wi h cycle images o GCin bold ed.
INTEGERS: 25 (2025) 8
3. The Hoey-Sloane Mul ig aph
We begin by s a ing and p o ing a esul which shows ha an edge label (d1, d2)
canno appea on wo o mo e dis inc edges o Γ.
Theo em 5. I c1, c2,ˆc1,and ˆc2a e s a es on Γ,and (d1, d2)is an inpu associa ed
wi h he ansi ions (c1, c2)and (ˆc1,ˆc2), hen (c1, c2) = (ˆc1,ˆc2).
P oo . By Equa ion (1), we ha e bo h bc2−c1=nd2−d1and bˆc2−ˆc1=nd2−d1.
Reducing bo h equa ions modulo b, we ha e c1≡d1−nd2≡ˆc1(mod b).Since c1
and ˆc1a e less han nby de ini ion, i ollows ha c1= ˆc1.A ou ine calcula ion
hen shows ha c2= ˆc2.
We now show ha any edge (d1, d2) o Minduces some ansi ion (c1, c2) on Γ.
Theo em 6. Le (d1, d2)be an edge o M. Then, he e a e in ege s 0≤c1≤n−1
and 0≤c2≤n−1such ha bc2−c1=nd2−d1.
P oo . F om ou assump ion, we know ha λ(d1+ (b−n)d2)≤n−1.Then, d1+
(b−n)d2≡d1−nd2≡c1(mod b),whe e 0 ≤c1≤n−1.I ollows ha nd2−d1≡
−c1(mod b).We hen ha e, o some in ege c2, ha nd2−d1=bc2−c1.In
ano he o m, bc2=nd2−d1+c1, om which we may say ha −b−1≤bc2≤
n(b−1) + n−1=nb −1.Thus, 0 ≤c2≤n−1,and he p oo is comple e.
Wi h Theo ems 5 and 6, we may now de ine a di ec ed, labeled mul ig aph which
we will call he (n, b)-Hoey-Sloane mul ig aph.
De ini ion 6. Le Nbe he collec ion o non-nega i e in ege s less han n. We map
each edge (d1, d2)o M o he mul i-edge (c1, c2)inN×N, which uniquely sa is ies
Equa ion (1), o o m a labeled mul i-edge, which we may isualize in he same
ashion as Figu e 3. Taking Nas he collec ion o e ices, along wi h he collec ion
o labeled mul i-edges de ined abo e, we will call his cons uc ion he (n, b)-Hoey-
Sloane mul ig aph. To dis inguish he mul ig aph om he usual (n, b)-Hoey-Sloane
g aph Γ,we will deno e he (n, b)-Hoey-Sloane mul ig aph as ∆.
We no e ha ∆ is simply an al e na i e ep esen a ion o Γ,whe e each mul i-
edge has a unique elemen om Mas a label, a he han a single edge wi h a
collec ion o inpu s om M. Fo his eason, when e e encing ∆,we will e ain he
ini e-s a e-machine e minology used when e e encing Γ.
We now p o ide wo simple examples o he abo e de ini ion.
Example 3. The (2,4)-mo he g aph Mis seen in Figu e 5. Mapping each edge
o M o i s mul i-edge uniquely de e mined by Equa ion (1), we ob ain he (2,4)-
Hoey-Sloane mul ig aph ∆ in Figu e 6.
INTEGERS: 25 (2025) 9
0
1
2
3
Figu e 5: The (2,4)-mo he g aph.
0
s a 1
(2,3)
(0,2)
(1,0)
(3,1)
(0,0)
(2,1)
(3,3)
(1,2)
Figu e 6: The (2,4)-Hoey-Sloane mul ig aph.
Example 4. The (3,4)-mo he g aph Mis displayed in Figu e 7. Mapping each
edge o M o i s mul i-edge, we ob ain he (3,4)-Hoey-Sloane mul ig aph ∆ shown
in Figu e 8.
0
1
2
3
Figu e 7: The (3,4)-mo he g aph.
INTEGERS: 25 (2025) 16
As shown in Example 2, he mul ise union
C0⊎C1⊎C1⊎C2⊎C2={(9,9),(8,2),(8,2),(2,8),(2,8),(7,1),(7,1),(1,7),(1,7)}
may be o de ed in o pe mu iple s ings. We e i y his by examining he mul i-
image union ∆0⊎∆1⊎∆1⊎∆2⊎∆2co esponding o he abo e mul ise union o
cycles, shown in Figu e 12.
0
s a 3
(2,8)
(2,8)
(7,1)
(7,1)
(8,2)
(8,2)
(1,7)
(1,7)
(9,9)
Figu e 12: The mul i-image union ∆I= ∆0⊎∆1⊎∆1⊎∆2⊎∆2co esponding o
he mul ise union CI=C0⊎C1⊎C1⊎C2⊎C2o mo he -g aph cycles.
Since he mul i-image union is L-Eule ian, we see, by Co olla y 2, ha we may
o de he mul ise union C0⊎C1⊎C1⊎C2⊎C2in o pe mu iple s ings by a e sing
Eule ian ci cui s beginning and ending wi h he ze o s a e on ∆0⊎∆1⊎∆1⊎∆2⊎∆2.
Two examples o hese can be ound in Example 2.
On he o he hand, as claimed bo h in Example 2 and in [11], he mul ise union
C1⊎C1⊎C2canno be o de ed in o pe mu iple s ings. Again, we examine he
co esponding mul ig aph union o mul i-images ∆1⊎∆1⊎∆2.
0
s a 3
(2,8)
(2,8)
(7,1)
(8,2)
(8,2)
(1,7)
Figu e 13: The mul i-image union ∆I= ∆1⊎∆1⊎∆2co esponding o he mul ise
union CI=C1⊎C1⊎C2o mo he -g aph cycles.
Al hough ∆1⊎∆1⊎∆2con ains he ze o s a e and is s ongly connec ed, we see ha
he indeg ees and ou deg ees a bo h e ices a e unequal. Thus, he mul ig aph
INTEGERS: 25 (2025) 17
is no L-Eule ian, and he condi ions o Co olla y 2 a e no me . Consequen ly,
C1⊎C1⊎C2canno be o de ed in o a pe mu iple s ing.
5. Summa y, Conclusions, and Fu u e Wo k
In [11], he ques ion is aised ega ding su icien condi ions which allow o he
o ma ion o pe mu iple s ings. In his pape , we ha e p o ided such a condi ion,
which leads o he ollowing equi alence: a mul ise union o mo he -g aph cycles
can be o de ed in o a pe mu iple s ing i and only i he mul ig aph union o
co esponding cycle mul i-images is L-Eule ian ( ha is, i i con ains he ze o s a e,
is s ongly connec ed, and he indeg ee is equal o he ou deg ee a each e ex).
F om he abo e conside a ions, we see ha coun ing pe mu iples wi h a ixed
base, mul iplie , and leng h, and a ixed mul ise o digi s, is educed o coun ing
Eule ian ci cui s o a pa icula s ongly-connec ed mul i-image union con aining
he ze o s a e ha ing equal indeg ee and ou deg ee a each e ex. Coun ing Eule-
ian ci cui s o di ec ed g aphs may be accomplished in polynomial ime using he
BEST algo i hm [17]. Mul ig aph a ia ions also exis [3]. Tha said, i we li he
cons ain o a ixed mul ise o digi s, hen coun ing pe mu iples o a ixed base,
mul iplie , and leng h ℓ, becomes a p oblem o inding all mul i-image unions which
a e L-Eule ian and ha e exac ly ℓmul i-edges. We a e unce ain o he di icul y o
his la e p oblem, and i p esen s an a ea o u he s udy.
Adding o he di icul ies p esen ed abo e, o la ge bases and mul iplie s, he
numbe o cycle mul i-images inc eases apidly. Fo example, as s a ed in [10], he e
a e 986 cycles o he (4,10)-mo he g aph. Thus, conside ing (4,10)-pe mu iples o
a ixed leng h ℓ, he e a e a e y la ge numbe o possible cycle mul i-image unions
o conside . Fil e ing hese possibili ies down o hose which a e L-Eule ian appea s
o be a di icul ask, and we lea e i o u u e e o s.
As men ioned in [10], he me hods p esen ed he e may be applied o he mo e
speci ic palin iple p oblem whe e σis he e e sal pe mu a ion. Finding palin iple
numbe s means ha we only need o examine he cycle mul i-images o mo he -
g aph 1- and 2-cycles. Howe e , inding palin iple s ings, which ha e he e y
pa icula o m
(d0, dk)(d1, dk−1)···(dj, dk−j)···(dk−j, dj)···(dk−1, d1)(dk, d0),
seems o be mo e di icul han one would expec ; hese a e no ob ious when
examining he Hoey-Sloane g aph o he indi idual cycle mul i-images. This is
ye ano he open ques ion which could ad ance ou unde s anding o palin iple
numbe s.
In con as o he abo e, o he e y speci ic case o palin iple numbe s when n+1
di ides b, Sloane [16] shows ha he numbe o k+1-digi (n, b)-palin iples, o k≥3,
INTEGERS: 25 (2025) 18
is F⌊k+1
2⌋−1,whe e Fmis he m h Fibonacci numbe . Res a ing his esul in e ms
o he pe mu iple class Cconside ed in Example 7, he e a e F⌊k+1
2⌋−1palin iple
s ings o leng h k+ 1.O he signi ican in ege sequences which migh a ise when
conside ing he gene al pe mu iple p oblem p esen s ano he open in i a ion o
u he in es iga ion.
We conclude by p esen ing some ques ions ela ing o he “de i ed-pe mu iple”
p oblem men ioned by [8, 9, 10]. A base-bpe mu iple (dk, . . . , d0)bis de i ed i i s
ca ies cj, no including he i ial ca y c0= 0,a e he digi s o a base-npe mu-
iple (ck, ck−1, . . . , c1)n.This phenomenon is illus a ed by he (6,12)-pe mu iple
(10,3,5,1,8,6)12 = 6 ·(1,8,6,10,3,5)12 whose non- i ial ca ies a e he digi s
o he (2,6)-palin iple (4,3,5,1,2)6= 2 ·(2,1,5,3,4)6.I we allow o leading
digi s which a e ze o, we ha e ano he pai o examples ela ed o one ano he :
conside ing he (2,3)-palin iple (2,1,0,1)3= 2 ·(1,0,1,2)3, he (3,6)-pe mu iple
(2,1,0,4,3)6= 3 ·(0,4,2,1,3)6has he ca y ec o (2,1,0,1,0),and he (6,12)-
pe mu iple (8,1,6,4,3,0)12 = 6·(1,4,3,0,8,6)12 has he ca y ec o (2,1,0,4,3,0),
whose non- i ial en ies a e he digi s o he p e ious example. F om he mul i-
g aph pe spec i e de eloped he e, he de i ed-pe mu iple p oblem may be posed
as he ollowing: gi en a base-npe mu iple (ck, ck−1, . . . , c1)n, ind an (n, b)-Hoey-
Sloane mul ig aph o which he ci cui (0, c1, . . . , ck−1, ck,0) may be a e sed by
using a collec ion o inpu s which is a mul ise union o (n, b)-mo he -g aph cycles.
The abo e examples na u ally lead o se e al ques ions: Gi en (dk, . . . , d0)b,de-
i ed om (ck, ck−1, . . . , c1)n,unde wha condi ions can we ind a (b,ˆ
b)-pe mu iple
de i ed om (dk, . . . , d0)b? A e he e cases o which his p ocess may be con inued
inde ini ely? Can en i e pe mu iple classes (see De ini ion 3) be cons uc ed om
o he s? Wha la ge pa e ns migh exis be ween hese classes?
O he ques ions ega ding he gene al p oblem may be ound in [8, 9].
Acknowledgemen . We a e g a e ul o he anonymous e e ee o hei ime, as
well as hei alued sugges ions and co ec ions which g ea ly enhanced he quali y
o his wo k.
Re e ences
[1] J. Bang-Jensen and G. Z. Gu in, Dig aphs: Theo y, Algo i hms and Applica ions, Sp inge ,
London, 2009.
[2] X. Fabe and J. G an ham, On in ege s whose sum is he e e se o hei p oduc , Fibonacci
Qua . 61(1) (2023), 28-41.
[3] M. Fa ell and L. Le ine, Mul i-Eule ian ou s o di ec ed g aphs, Elec on. J. Combin. 23(2)
(2016), P2.21.
[4] S. Gu man, On cyclic numbe s, Ame . Ma h. Mon hly 41(3) (1934), 159-166.
INTEGERS: 25 (2025) 19
[5] D. J. Hoey, Un i led online a icle (no pee - e iewed). A ailable om OEIS Founda ion
Inc. (1992), The On-Line Encyclopedia o In ege Sequences a h ps://oeis.o g/A008919/
a008919. x .
[6] B. V. Hol , Some gene al esul s and open ques ions on palin iple numbe s, In ege s 14 (2014),
#A42.
[7] B. V. Hol , De i ed palin iple amilies and hei palinomials, In ege s 16 (2016), #A27.
[8] B. V. Hol , On pe mu iples ha ing a ixed se o digi s, In ege s 17 (2017), #A20.
[9] B. V. Hol , A me hod o inding all pe mu iples wi h a ixed se o digi s om a single known
example, In ege s 24 (2024), #A88.
[10] B. V. Hol , Finding pe mu iples o a known base and mul iplie , In ege s 25 (2025), #A13.
[11] B. V. Hol , U ilizing he e lec i e symme y o he mo he g aph in inding new pe mu iple
classes om old, p ep in , a Xi :2504.17158 2.
[12] D. Kalman, F ac ions wi h cycling digi pa e ns, College Ma h. J. 27(2) (1996), 109-115.
[13] L. H. Kend ick, Young g aphs: 1089 e al., J. In ege Seq. 18 (2015), A icle 15.9.7.
[14] B. Qu and S. J. Cu an, An unexpec ed digi pe mu a ion om mul iplying in any numbe
base, in Combina o ics, G aph Theo y and Compu ing, Sp inge , Cham, 2022, 13-31.
[15] D. Silbe ge , Eule ian di ec ed mul ig aphs, p ep in , a Xi :2408.12699.
[16] N. J. A. Sloane, 2178 and all ha , Fibonacci Qua . 52(2) (2014), 99-120.
[17] T. an Aa denne-Eh en es and N. G. de B uijn, Ci cui s and ees in o ien ed linea g aphs,
Bull. Belg. Ma h. Soc. Simon S e in 28 (1951), 203-217.
[18] R. Webs e and G. Williams, On he ail o e e se di iso s: 1089 and all ha ollow, Ma h.
Spec um 45 (2012/2013): 96-102.
[19] A. L. Young, k- e e se mul iples, Fibonacci Qua . 30 (1992), 126-132.
[20] A. L. Young, T ees o k- e e se mul iples, Fibonacci Qua .,30 (1992), 166-174.
