[seqfan] Re: Two neighboring digits sum up to a prime

Maximilian Hasler maximilian.hasler at gmail.com
Fri Apr 27 22:07:29 CEST 2012

```On Fri, Apr 27, 2012 at 2:38 PM, Hans Havermann wrote:
>
> Aren't there a total of 524287 subsets? Do we know that most of these are
> trivial?

Not quite - e.g., any set without terms in [10,...,18] leads to a
finite sequence,
which ends as soon as a term ending in the largest admissible digit is reached.
(Some examples below.)

Maximilian

newS(99,[0,1],1) = 0,1.

newS(5,[0,1,2],1) = 0,1,10,2.

newS(5,[0,1,2,3],1) = 0,1,2,10,3.

newS(99,[0,1,2,3,4],1)
= 0,1,2,10,3,11,12,13,100,4.

newS(99,[0,1,2,3,4,5],1)
= 0,1,2,3,10,4,11,12,13,14,100,5.

newS(99,[0,1,2,3,4,5,6],1)
= 0,1,2,3,10,4,11,5,12,13,14,15,100,6.

newS(99,[0,1,2,3,4,5,6,7],1)
= 0,1,2,3,4,10,5,11,6,12,13,14,15,16,100,7.

newS(99,[0,1,2,3,4,5,6,7,8],1) =
0,1,2,3,4,10,5,11,6,12,13,14,15,16,17,100,7,101,20,8.

newS(99,[0,1,2,3,4,5,6,7,8,9],1) =
0,1,2,3,4,5,10,6,11,7,12,13,14,15,16,17,18,100,8,101,20,9.

newS(99,[0,1,9],1) = 0,1,8,10,9.

newS(99,[0,1,8,9],1) =
0,1,7,2,6,3,5,4,44,45,35,36,26,27,10,8,17,18,100,9.

newS(49,[0,1,10],1) =
0,1,9,10,19,100,101,91,910,191,919,1000,1001,9100,1010,1019,1910,
1919,10000,10001,9101,9191,91000,10010,10019,10100, 10101,
91001,91010,10191,91019,19100,19101,91910,19191,91919,100000,...
(infinite)

newS(49,[1,10],1) =
1,9,10,19,101,91,910,191,919,1010,1019,1910,1919,10101,9101,9191,
91010,10191,91019,19101,91910,19191,91919,101010,101019,101910,...
(infinite)

(inefficient) PARI code:
isok(a,M)={ a[1]=Str(a[1]); for(i=2,#a=Vecsmall(concat(a)),
bittest( M, a[i-1]+a[i]-96) || return);1}
newS(N,S,v)={ my( L, a=L=S[1], u=1<<L); S=sum(i=1,#S,1<<S[i]);
for( n=1,N, v & print1(L","); for( t=1,9e9, bittest(u,t) & next;
isok( [ L,t ], S ) || next; a=concat(a,L=t); u+=1<<t; break)); a}

```