Generalizing TOTP Anagram Counting for Different Bases

Math
Anagrams
Combinatorics
TOTP
OEIS
Author

Jean-François Im

Published

April 12, 2026

While working on the submission for A394980 — the count of anagram pairs in halves of TOTP codes — one of my more mathematically inclined friends asked if this was just a different series in disguise. I couldn’t find any other matching sequences initially, but when working on it, the other dimension that I didn’t explore initially was the assumption that one is working with base 10, as would be the case for regular TOTP codes. Changing the base to different values is where the plot thickens.

Changing the code to use different values for the base is relatively trivial, so for bases 2 to 10, the first 25 terms are:

Code 
from itertools import product, combinations_with_replacement
from collections import Counter
from math import factorial, perm
import time

def distinct_perms(seq):
    """Number of distinct permutations of seq."""
    counts = Counter(seq)
    denom = 1
    for k in counts.values():
        denom *= factorial(k)
    val = factorial(len(seq)) // denom
    return val

def partitions(n, max_part=None):
    """Generate all integer partitions of n."""
    if max_part is None:
        max_part = n
    if n == 0:
        yield []
        return
    for first in range(min(n, max_part), 0, -1):
        for rest in partitions(n - first, first):
            yield [first] + rest

def partition_freq(p, base=10):
    """Number of distinct prefixes of length n with the shape described by partition p."""
    num = perm(base, len(p))
    group_sizes = Counter(p).values()
    denom = 1
    for g in group_sizes:
        denom *= factorial(g)
    return num // denom

def expand(p):
    """Turns a partition into a sequence, eg. [4,1,1] -> [1,1,1,1,2,3]"""
    result = []
    for i, count in enumerate(p):
        result.extend([i] * count)
    return result

for base in range(2,11):
    seq = [sum(partition_freq(p, base) * (distinct_perms(expand(p))**2) for p in partitions(n)) for n in range(1,26)]
    print(f'b={base}: {",".join(map(str, seq))}')
b=2: 2,6,20,70,252,924,3432,12870,48620,184756,705432,2704156,10400600,40116600,155117520,601080390,2333606220,9075135300,35345263800,137846528820,538257874440,2104098963720,8233430727600,32247603683100,126410606437752
b=3: 3,15,93,639,4653,35169,272835,2157759,17319837,140668065,1153462995,9533639025,79326566595,663835030335,5582724468093,47152425626559,399769750195965,3400775573443089,29016970072920387,248256043372999089,2129158861755559587,18301184259810988815,157626238006835196237,1360135024740956026161,11756409817108040588403
b=4: 4,28,256,2716,31504,387136,4951552,65218204,878536624,12046924528,167595457792,2359613230144,33557651538688,481365424895488,6956365106016256,101181938814289564,1480129751586116848,21761706991570726096,321401321741959062016,4766118425002290943216,70937237822612227230784,1059325264441498545599488,15867288561475917552050176,238332503119317701296868416,3588998891197749315801781504
b=5: 5,45,545,7885,127905,2241225,41467725,798562125,15855173825,322466645545,6687295253325,140927922498025,3010302779775725,65046639827565525,1419565970145097545,31249959913055650125,693192670456484513025,15480814434909059226825,347819791175860063294125,7857219150562637891693385,178365050610159455909952525,4067061957851359126795514325,93113307750242799253647686025,2139705756334600522205487928425,49337502810931248099790152915405
b=6: 6,66,996,18306,384156,8848236,218040696,5651108226,152254667436,4229523740916,120430899525096,3499628148747756,103446306284890536,3102500089343886696,94219208840385966096,2892652835496484004226,89662253086458906345036,2802887038905690746642916,88285112311736445352115976,2799753247995266147347843956,89333847417312523954034046936,2866354076060681446555954224696,92437346938232317505833680390576,2994900985489170290757597878329836,97447591912171214828256883106131656
b=7: 7,91,1645,36715,948157,27210169,844691407,27840317995,961404929485,34453695086041,1272342313935007,48163840784596201,1861408648486464175,73216844934326184595,2923876764438202454245,118311576139002457750315,4843019129955904050049645,200285107637533495666136425,8358772615816778247959630575,351714866444503250286117523465,14908928917141407766153378543855,636226231030579337275522117546915,27316683312186657375742935536430325,1179425650762021100313399983695203625,51184907683955175375444981664073129407
b=8: 8,120,2528,66424,2039808,70283424,2643158400,106391894904,4518833256512,200396211454720,9205443151733760,435368682010660000,21100379936684418560,1044115187294444772480,52597451834668445910528,2691037806733052553149304,139567074682665782246950080,7326035505602088571550898624,388692676307093660214513983232,20821560514105053341045830189824,1125071052804606862976953994944512,61270967628785336626069622639938560,3360729604535080838933867116477304832,185546031656019274031650908498763590816,10305688197366722917347399525269829719808
b=9: 9,153,3681,111321,3965409,159700401,7071121017,337386574809,17091486402849,909016606157553,50322658889918457,2880377856928886769,169569570177502573113,10224662030381995585353,629363959548197255942481,39439533486823544576759769,2510598661017963812643872673,162048024871184932602477539121,10589311049996692605851511195321,699665020890634054314125660348721,46691291797797628279076275449673209,3144108851688963610024995327698430153,213463410619979489585755003304528851281,14601839580495416551702129260310203023601,1005731803116618747973879291182068848700409
b=10: 10,190,5140,175870,7132060,329009500,16786131400,928136093950,54775566167500,3410496772665940,222005754890212600,15000987483726651100,1046188137708903907000,74962723424363171666200,5498130019391836779330640,411530535654245301470621950,31356088574298606320386653100,2427021041017043491153965921700,190503335542483372330410996741400,15141611551571136170888372040881620,1217139074924843939858814351399207400,98842200132473370747145638230967749800,8101728898006244345372661851453503553200,669726723998568836522230181105574128110300,55795274602503578824222289822443655978969560

Interestingly, some of these sequences do appear to exist in the OEIS! Specifically, as of the time of writing this blog post, these ones match the first terms generated:

b=2
A000984 Central binomial coefficients: \(\binom{2n}{n} = \frac{(2n)!}{(n!)^2}\)
b=3
A002893 \(a(n) = \sum_{k=0}^{n} \binom{n}{k}^2 \binom{2k}{k}\)
b=4
A002895 Domb numbers: number of 2n-step polygons on diamond lattice. \(a(n) = \sum_{k=0}^{n} \binom{n}{k}^2 \binom{2k}{k} \binom{2(n-k)}{n-k}\)
b=5
A169714 The function \(W_5(2n) = \int_0^1 \cdots \int_0^1 \left(\sum_{i=1}^{5} \cos(2\pi x_i)\right)^{2n} dx_1 \cdots dx_5\)
b=6
A169715 The function \(W_6(2n) = \int_0^1 \cdots \int_0^1 \left(\sum_{i=1}^{6} \cos(2\pi x_i)\right)^{2n} dx_1 \cdots dx_6\)
b=8
A385286 \(a(n) = (n!)^2 [x^n]\, {}_0F_0\!\left(\left[\,\right]; \left[1\right]; x\right)^8\)

Unfortunately, it’s beyond my current mathematical ability to prove that they’re equivalent, but there are a few things that I can mention.

For \(b=5\) and \(b=6\), Proposition 1 on page 6 of Borwein et al (2011)1 mentions the definition of \(W_n(2k)\)

\[W_n(2k) = \sum_{a_1+\cdots+a_n=k} \binom{k}{a_1,\ldots,a_n}^2\]

which on page 7, they mention is also the exact same formula as the definition of the combinatorial sums of multinomial coefficients squared

\[f_n(k) = \sum_{a_1+\cdots+a_n=k} \binom{k}{a_1,\ldots,a_n}^2\]

Those sums are discussed in Richmond and Shallit (2008)2 in which they mention that \(f_n(k)\) counts abelian squares — strings \(xx'\) of length \(2k\) over an alphabet with \(n\) letters such that \(x'\) is a permutation of \(x\) — and that \(f_2(n)\) matches sequence A000984, \(f_3(n)\) matches sequence A002893, \(f_4(n)\) matches sequence A002895.

Given that my TOTP problem matches with the definition of what \(f_{n}(k)\) would be in Richmond and Shallit for a string of length \(2k\) and an alphabet of \(n\) letters, we can then rewrite that the \(k\)th term of my sequence is \(a_{b}(n)=f_b(k)\). This allows us to conclude that:

b=2
\(a_{2}(n)=f_2(k)\), which Richmond and Shallit mention is A000984
b=3
\(a_{3}(n)=f_3(k)\), which Richmond and Shallit mention is A002893
b=4
\(a_{4}(n)=f_4(k)\), which Richmond and Shallit mention is A002895
b=5
\(a_{5}(n)=f_5(k)\), since \(f_5(k)=W_5(2k)\) by definition, this is A169714
b=6
\(a_{6}(n)=f_6(k)\), since \(f_6(k)=W_6(2k)\) by definition, this is A169715

This leaves us with the case of \(b=8\). This appears to match A385286, and in their definition, they mention that

We regard this sequence in the list of sequences n -> A287316(n, 2^k) for k = 3.

and they cross-reference

A000984 (k=1), A002895 (k=2), this sequence (k=3), A287316

This would suggest that the pattern is \(f_{2^k}\), so for A000984 \(f_2=f_{2^1}\), and for A002895 \(f_4=f_{2^2}\), meaning that A385286 is effectively \(f_{2^3}\) in disguise and thus the same as this sequence for \(b=8\).

Of note is the fact that \(b \in \{7,9\}\) aren’t in the OEIS, which is probably an interesting artifact of nobody ever needing them or studying them in a way that would lead them to add them to the OEIS, rather than them being completely novel. Given that Richmond and Shallit only cover \(f_n\) for \(n \leq 6\), and \(f_8\) is there due to \(2^k\) for \(k=3\), that would explain the lack of \(f_7\) and \(f_9\) in the OEIS.

Still, for a random shower thought about TOTP codes, it was quite an interesting mathematical rabbit hole to fall into.

Footnotes

  1. Borwein, J. M., Nuyens, D., Straub, A., & Wan, J. (2011). Some arithmetic properties of short random walk integrals. The Ramanujan Journal, 26(1), 109–132. doi:10.1007/s11139-011-9325-y↩︎

  2. Richmond, L. B., & Shallit, J. (2008). Counting Abelian squares. The Electronic Journal of Combinatorics, 16. arXiv:0807.5028↩︎