What is the smallest prime p>3 dividing the (right) concatenation of all numbers <=p in base 3?

[Jianing Song]

Hello everyone,

In each base b, I was interested in finding the smallest nontrivial p such that p divides the (right) concatenation of all numbers <=p in base b. By "nontrivial" I mean p not dividing b(b-1): divisors d of b or odd divisors d of b-1 trivially satisfy that they divide that concatenation. So for example, in base 10 the answer is 8167 (see A072712).

Now I am coping M. F. Hasler's program in A029455 to give one searching for the smallest prime p:

(PARI) a(base) = c=0; for(d=1, oo, for(n=d, -1+d*=base, c=c*d+n; if(isprime(n) && (base*(base-1))%n!=0 && c%n==0, return(n))); d--)

so we can calculate starting from base 2:

3, ?, 2281, 23, 103, 61, 13, 47, 8167, 281, 29, ?, 19, 6829, 83, 809, 208631, 47, 71, 79, ?, ?, ...

The values corresponding to bases 3, 13, 22, 23 are marked with "?".

But if the answer in same b is very large then it should be very hard to find: For each n the concatenation of 1 through n has O(n log n) digits, so finding its remainder modulo n requires O(n (log n)^2) bit operations. Taking the sum of n means that to calculate terms up to n, the time complexity is O(n^2 (log n)^2). I guess some optimizations may be applied, but still we face something at the order of n^2.

Here we are in the situation of finding Wieferich primes or k-Wall-Sun-Sun primes: we conjecture that there are infinitely many (because we can't give a proof of the contrary), we know at most a handful of terms in each base, and in some bases (like 1-Wall-Sun-Sun) we don't know any result at all.

So I was wondering if everyone is interested in finding the smallest nontrivial p dividing the concatenation of all numbers <=p in base 3? Or in other bases? Perhaps someone have studied this sequence in the litterature before (and proved that such primes do not exist)? Thank you for your attention, for your time and any help in advance! :)

[Jianing Song]

I forgot to say that for base 3 such prime must be at least 10^7; see b-file of A029448.

Jianing Song <jianing...@gmail.com> 于2026年4月26日周日 17:17写道：

--
You received this message because you are subscribed to a topic in the Google Groups "SeqFan" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/seqfan/XPC356TFyO8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/0e369b93-5a1f-458a-b629-b0e72b3c6d7fn%40googlegroups.com.

[Jack Brennen]

I believe that the ? for base 13 can be replaced with 6569023.  I'd want to double-check it first to make sure there are no smaller solutions, but that's at least an upper bound.

--
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.

[Jianing Song]

That's nice, thanks for your calculation!

[Michael Branicky]

I confirm Jack's base 13 = 6569023  

and compute base 23 as 1363221317 

To view this discussion visit https://groups.google.com/d/msgid/seqfan/92328608-dd34-4e33-b980-8119ebb30c24n%40googlegroups.com.

[Jianing Song]

Wow, remarkable! So I guess the base 3 case is very resisting, right?

[Michael Branicky]

For base 3, I obtained 37347358781

Regards,

Michael

To view this discussion visit https://groups.google.com/d/msgid/seqfan/6fcc2120-c2db-4e40-a8dc-26d6dde3d8dfn%40googlegroups.com.

[Jianing Song]

Wow that's ready to make it fits into a new OEIS sequence now! Would you like to share your algorithm of finding this? Or do you have any remark for the sequence? Thanks really a lot to your contribution!

[dan strader]

Michael's base 13 got its double-check in-thread, but 3 and 23 maybe hadn't been independently confirmed, so... I've recomputed every entry in the table with an independent implementation including: 6569023, 1363221317 and 37347358781. All 21 agree, no discrepancies.

I got there with a per-p test rather than a running bignum: O(log^2 p) modular operations per prime, so the n^2 barrier doesn't bind. Happy to write up the identity or share the code if that's useful to anyone.

Is base 22 still open / how far has it been pushed? I have it clean to 10^11, but I assume that's ground already covered.

Happy to put a GPU on it and go a couple of orders further on base 22 if that would help rather than duplicate.

-DS