[seqfan] Re: Meertens numbers

[David Applegate]

I've pushed the search a bit further; there is no other Meertens number
below 10^45.

I also searched for Meertens numbers in other bases between 2 and 16.
The results are in https://oeis.org/A246532.

The C++ code I used (using GMP for extended-precision arithmetic) is
also attached, at https://oeis.org/A246532/a246532.cc.txt.

The key to pushing the search forward was the observation that if
   x * 10^k + y
is a k+j-digit Meertens number (with 0<=y<10^k and 10^(j-1)<=x<10^j),
(i.e., x is a j-digit prefix in a prefix-based search, or y is a
k-digit suffix in a suffix-based search), then
   x * 10^k + y = godel(x) * godel(y,j+k)
where godel(x) is the godel-encoding (A189398), and godel(x,d) is the
godel-encoding as if x as d digits.

This means
   y === -x * 10^k (mod godel(x))
or
   x * 10^k === -y (mod godel(y,j+k))

So, if godel(x) is around 10^k, there are only a few possible y that
satisfy the congruence and are <= 10^k, and similarly for the suffix
search (except that solving the congruence involves a bit more work).

David Applegate


> From seqfan-bounces at list.seqfan.eu Thu Aug 21 17:15:06 2014
> Date: Thu, 21 Aug 2014 17:13:52 -0400
> From: Max Alekseyev <maxale at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: Meertens numbers

> I've pushed the lower bound further to 10^20.
> Regards,
> Max

> On Mon, Aug 18, 2014 at 8:23 PM, Max Alekseyev <maxale at gmail.com> wrote:

> > I've checked numbers below 10^19 -- no new Meertens founds.
> > Regards,
> > Max
> >
> >
> > On Fri, Aug 15, 2014 at 3:53 PM, Hans Havermann <gladhobo at teksavvy.com>
> > wrote:
> > > For an overview see: https://oeis.org/A189398
> > >
> > > One website has a person suggesting that another solution would be >
> > 10^17.
> > >
> > > _______________________________________________
> > >
> > > Seqfan Mailing list - http://list.seqfan.eu/
> >

> _______________________________________________

> Seqfan Mailing list - http://list.seqfan.eu/