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 kth 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↩︎