RFE August 2026: repeated numbers in Pi

[Sean A. Irvine]

Hi,

This month something for the Pi fanatics.

Can someone please take a look at A086183 (and related sequences) and provide an explanation and/or program? In particular, I do not understand the initial terms of this sequence, even if I can get a general sense of what is happening here.

I track these requests for enhancement here (a few others still remain open):

https://oeis.org/wiki/User:Sean_A._Irvine/Requests_for_Enhancements#Requests_for_Enhancements

Sean.

[Aitzaz Imtiaz]

>   In particular, I do not understand the initial terms of this sequence, even if I can get a general sense of what is happening here.

I think I made some sense out of it. If we take the value of Pi as: "3.14159265," I will try to explain it informally.

We need to take a pivot and a substring, so that the pivot is last term of first string, and first term of last string. Compare them to find similar substring and biggest number out of that substring is valid term.

n = 1: '3' '3' ==> 3 = 3

n = 2: '31' '14' ==> 1 = 1

n = 3: '314' '415' ==> 1, 4 = 4

.
.
.
n = 13: '3141592653589' ' 9793238462643' ==> 1, 2, 3, 4, 6, 8, 9, 26 = 26

Aitzaz.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAL0FETm%2Bmre6Uo7c9MBWihQVSMOvJUysLD4qfmoK3QOtxYv6UA%40mail.gmail.com.

[Sean A. Irvine]

Ah, thank you. I think that is correct. I did not consider that the "next n positions" would mean overlap by 1 position.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CA%2BZ5DMX3usLKsJAnOyw-B%2B0ToL1w8R94C4JNru-mNxCbvm_M7Q%40mail.gmail.com.

[Dave Consiglio]

pi = "31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989"


for n in range(50):
    first_chunk = pi[0:n+1]
    second_chunk = pi[n:n*2+1]
    #print(first_chunk, second_chunk)
    best = 0
    for le in range(1,n+1):
        for x in range(0,le):
            for y in range(x+1,le+1):
                check = first_chunk[x:y]
                if check in second_chunk and int(check) > best:
                    best = int(check)
                    #print(first_chunk,second_chunk)
    print(n,best)
       

Here's some quick Python. 

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAL0FETnmi1iksoXUSnYgzt88hzTgr1N_Z8EMJ0y1yo5vvnqMRg%40mail.gmail.com.

[Lucas Brown]

Rather than hard-coding the digits of pi, it would be better to do something like:

from gmpy2 import const_pi

from math import log2

pi = str(const_pi(log2(10) * n))

where n is the desired number of decimal digits.  The gmpy2 package is not in the Python standard library, but it can be installed via pip.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAE7BzufSfKOZXkC0u7JHpgaw_MJF2n9UgGpBvTq1oa_reJRyYg%40mail.gmail.com.

[Dave Consiglio]

Thanks Lucas. Here's updated code (for 1000 terms):

from gmpy2 import const_pi, context
from math import log2


m = 1000
with context(precision=m) as ctx:
    pi = '3'+str(const_pi())[2:]


for n in range(m):

    first_chunk = pi[0:n+1]
    second_chunk = pi[n:n*2+1]

    best = 0
    for le in range(1,n+1):
        for x in range(0,le):
            for y in range(x+1,le+1):
                check = first_chunk[x:y]
                if check in second_chunk and int(check) > best:
                    best = int(check)

    print(n,best)
        

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CALSFKfgowu0W8RC1VMCwm36VG5tbi2LX2mUQQZDqZ5pqp6UNRQ%40mail.gmail.com.

[Dave Consiglio]

sorry - caught a bug:

from gmpy2 import const_pi, context
from math import log2


m = 1000
with context(precision=m) as ctx:
    pi = '3'+str(const_pi())[2:]


for n in range(m):
    first_chunk = pi[0:n+1]
    second_chunk = pi[n:n*2+1]
    best = 0
    for le in range(1,n+1):

        for x in range(0,le+1):
            for y in range(x+1,le+2):

                check = first_chunk[x:y]

                #print(first_chunk,check)

[James McMahon]

Using Mathematica:

a[n_]:=Intersection[FromDigits/@Subsequences[RealDigits[Pi,10,n][[1]]],FromDigits/@Subsequences[Drop[RealDigits[Pi,10,2n-1][[1]],n-1]]][[-1]];Array[a,61]

Data agrees: {3,1,4,1,5,9,9,9,9,9,9,26,26,26,26,79,79,79,79,84,97,97,97,97,97,97,97,97,97,97,97,97,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592,592} 

[Dario Clavijo]

Hi,

With DP I think we can get O(n^3) as worst case because 3 loops and O(n^2) as average because the comparissons, I think this could be optimizable with LCS and unlock O(n log n):

from sympy import pi, N

def pi_digits(n):

    return str(N(pi, n + 20)).replace('.', '')[:n]

def sequence(m):

    d = pi_digits(2 * m + 10)

    for n in range(1, m + 1):

        f,s,b,m = d[:n], d[n - 1:2 * n - 1],0,0

        L = len(f)

        for x in range(L):

            if m: m -= 1

            while (x + m) < L and f[x:(x + m) + 1] in s: m += 1

            if m: b = max(b, int(f[x:(x + m)]))

        yield b

if __name__ == "__main__":

    for v in sequence(1000):

        print(v)

Best regards 

Darío 

To view this discussion visit https://groups.google.com/d/msgid/seqfan/27a7af2a-f889-4313-a902-5e27a9aa76d5n%40googlegroups.com.

[DONG HAOXUAN]

Hi Sean and all,

I took a closer look at A086183 and ended up writing a considerably faster exact implementation.

For a fixed (n), the program builds a suffix automaton for the first block (X_n) and scans the overlapping block (Y_n). At each ending position in (Y_n), it is enough to consider the longest suffix that also occurs in (X_n); after removing any leading zeros, this gives the largest candidate ending at that position. A precomputed next-nonzero table handles the zeros, and suffix ranks from an SA-IS suffix array are used to compare equal-length candidates exactly.

For computing all terms (a(1),\ldots,a(N)), the suffix automaton is extended incrementally as (n) increases, while the suffix ranks are built only once. The resulting complexity is

[
O(N^2)
]

time and (O(N)) working memory. A single specified term can be computed in (O(n)) time. The implementation does not use rolling hashes or probabilistic comparisons.

I also compared it with a faithful runnable transcription of Darío’s Python approach from this thread. Using the same exact digit file, suppressing sequence output, and timing only the core computation, I obtained approximately:

• (138times) faster at (N=500);
• (266times) faster at (N=1000).

These figures are naturally machine-dependent, but the gap increases with (N). Compared with the earlier direct-enumeration program, the difference is much larger, although Darío’s version seems the fairer baseline.

For verification, the package includes an independent brute-force oracle, exhaustive tests on small binary strings, randomized decimal tests, and an independent check of the SA-IS suffix ranks. The first 1000 terms agree term-by-term with the posted Python approach, and the known initial terms through (n=61) are also reproduced.

I have attached both the standalone C++20 source and a small package containing an English README, the correctness argument, CMake support, benchmark scripts, reference timings, and checksums.

This may be useful for adding a more efficient program and explanation to A086183.

Best,
Jason Dong

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CABjGZ_D86N_rkQ2kM9OXgXKOtJcpZTc2FEb0qF0uJ1AXcFAczQ%40mail.gmail.com.