Fw: OEIS A240563 - prime concatenation

[Richard Donovan]

Hi

https://oeis.org/A240563

Could someone please show me a slick J function to produce the OEIS A240563 sequence - prime concatenations, without the need for loops.

TIA

Richard

[Clifford Reiter]

Not sure it is "slick", but food for thought.

primeq=:1=#@q:

primeq 101

1

pcat=:,&.":

2 pcat 3

23

ifp=:{{if. primeq t=.y pcat x do. t else. y end.}}

~.] F:. ifp p: i. 15

23 2311 231131 23113147

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

[Clifford Reiter]

Some refinements:

NB. use built-in prime test

primeq=:1&p:

NB. to use extended integers

pcat=:".@(,&'x')@(,&":)

NB. to make ifp tacit

ifp=:{.`{:@.(primeq@{:)@:(],pcat~)

NB. to get the starting 2 and match oeis

]t=:~.''] F:. ifp p: i. 200x

2 23 2311 231131 23113147 23113147229 23113147229251 23113147229251577 23113147229251577857 23113147229251577857859 23113147229251577857859911 231131472292515778578599111123 2311314722925157785785991111231223

#t

13

NB. get a couple more

#t2=:~.''] F:. ifp p: i. 250x

15

[Michael Day]

Sorry to Richard - I meant to send to Forum,  not to him only!  Message follows...

Clifford sent useful ideas this afternoon.  Meanwhile I was trying to work up variations on 
my suggestions in previous correpondence with Richard on a similar sequence, A066064, 
in April. 

Cliff's construction returns the sequence with repeats,  before applying ~.     as in:

    ''] F:. ifp p: i. 10x

2 23 23 23 2311 2311 2311 2311 2311 2311

I hoped to avoid this repetition, and also to avoid lots of long concatenated primes,

but with limited success.  Cliff's function returns the first 40 to 50 elements in about

half the time of my approach.  But it's still quite nifty,  and not too hungry for space,

so I present it here anyway.   Basically,  I reproduce A080155 rather than A240563, 

ie the list of added primes rather than their successive concatenations.

NB. functions could be more one-line-ish,  but I was trying to time them with JPM.

nextp =: 4 p: ]     NB. next prime!

cat =: ".@(,&'x')@(,&":)   NB. cribbed from Cliff

NB. given a term in the sequence and the current last prime

NB. return the term with the next candidate prime OR

NB. the term with 1 less than the next required prime

NB. which is repeated on the next application,  thus closing

NB. the application using the power operator,  ^:_

fnsub1 =: {{
x, y - 1 p: x cat y =. nextp y 
}}/

NB.  eg

NB.    fnsub1 2311 11

NB.2311 13

NB. but

NB.   fnsub1 2311 30

NB.2311 30 NB. so no change,  so power operator quits.

fnsub  =: >:@{:@: (fnsub1^:_)
NB. eg 

NB.   fnsub 2311 11

NB. 31

fn  =: {{ 2 fn y
:
list  =. x                NB. eg 2 3 11
rep   =. 0 >. y - # list  NB. number of required elements
whole =. cat/ list        NB. eg 2311
for. i. rep do.
   list =. list, newp =. fnsub whole, {: list
   whole=. cat/whole, newp
NB. echo list;whole NB. debugging!
end.
list
}}

eg

   fn 10     NB.  reproduce elements of A080155
2 3 11 31 47 229 251 577 857 859
   (, cat/) fn 10
2 3 11 31 47 229 251 577 857 859 23113147229251577857859

2 5 $ (cat/\) fn 10    NB. reproduce elements of A240563. 

2 23 2311 231131 23113147

23113147229 23113147229251 23113147229251577 23113147229251577857 23113147229251577857859

NB. shape not reproduced here!

The number of terms shown in the OEIS page for A080155 is around 44,   using up ro 

around 5000 primes: 

      ts'fn 44'                NB. slower but leaner than Cliff's
1.0121 15136
      ts'_10{.": {:]t=:~.''''] F:. ifp p: i. 5000x'
0.579638 1.4405e6

We agree on the last new prime:

   {:fn 44
48523
   _5{.":   {:]t=:~.''] F:. ifp p: i. 5000x
48523

Greathouse's Pari GP function,  listed in the OEIS page for the concatenated list, A240563,  

takes about 13 seconds on my laptop,  running the Windows version,  for 44 terms,  so we're 

doing ok compared with a numerical function expert!  However, he doesn't offer a function 

for A080155,  which only lists the added primes,  not their concatenations.  That might be a bit

quicker in Pari GP.   (I don't have Mathematica or Maple.)

Cheers,

Mike

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

Virus-free.www.avast.com

[Richard Donovan]

Hi Michael

Thanks for your input.

I wrote a program (below) which does the trick!

I used a while loop which returned acceptable time and space usage for iterations up to 50,000 (ts 'pc 50000' ==> 11.736 112768.

I ran it a million iterations (see test "huge" which on my very old windows PC returned a result which took more than 30 minutes yet did not find a further value!).

I'm not sure if changing the While loop to ^:xyz would make it run any faster. I also have no idea how many more iterations would be necessary to find the next prime.

The OEIS highest prime has 31 digits compared to my 17 so there is a looooooong way to go!

Cheers,

Richard

==== J Function "pc", prime concatenation

NB. OEIS A240563 - prime concatenation

concat=:4 : 'x:". (":x),(":y)'"0

pc=: 3 : 0

iter=:y

NB. pc y => generate y iterations

base=: 2

r=:base

npi=:0

test=: base concat p:npi

while. iter > 0 do. iter=:iter-1

npi=:>:npi

test=: base concat p:npi

if. 1 p: test

do. base=: base concat p:npi

r=:r,base  

end.

end.

r

NOTES =: 0 : 0

  pc 100

2 23 2311 231131 23113147 23113147229 23113147229251

  #pc 100

7

  +./  1 p:  pc 100 NB. all prime?

1

 

_1{pc 100      NB. Last entry

23113147229251

  #":_1{pc 100 NB. digits

14

  ts 'pc 100'

0.0170754 108608

  pc 1000

2 23 2311 231131 23113147 23113147229 23113147229251 23113147229251577

  +./  1 p:  pc 1000

1

   _1{pc 1000

23113147229251577

     #":_1{pc 1000 NB. digits

17

   ts 'pc 1000'

0.0372346 112768

huge=: pc 1000000

,. huge

               2

              23

            2311

          231131

        23113147

     23113147229

  23113147229251

23113147229251577

    +./  1 p:  huge

1

)

---

From: 'Michael Day' via forum <fo...@jsoftware.com>
Sent: Sunday, June 08, 2025 21:35
To: fo...@jsoftware.com <fo...@jsoftware.com>
Subject: Re: [Jforum] Fw: OEIS A240563 - prime concatenation

[Mike Day]

One problem when I tried pc for large-ish primes;  concat fails for large 

arguments:

      1234567890 concat 23456789012345

123456789023456782974976

Perhaps you used another version of concat in your tests.  

BTW, if you move 

    iter=:iter-1

to the inner if end block,  the argument y controls the number of 

primes.

Cheers,

Mike

Sent from my iPad

On 9 Jun 2025, at 18:26, Richard Donovan <rsdo...@hotmail.com> wrote:



[trx2358...@yahoo.com]

The C version of the Möbius function on Rosetta code doesn’t calculate primes up front (let alone factoring of composites) but rather lets them fallout as a byproduct of the filter.  You might consider following that model.

https://rosettacode.org/wiki/Möbius_function 

Sent from Yahoo Mail for iPhone

[Michael Day]

Yes,  I have a mu function in my "fastmoeibius.ijs" script which pretty
well mirrors that C function - the script includes a similar C function, 
so I probably plagiarised it! 

mu =: 3 : 0
max   =. y
mu    =. 0, max#1
i     =. 1
rtmax =. <.%: max
while. rtmax >: i =. 4 p: i do.
      j   =. i * >: i.max <.@% i
      muj =. - i * j{mu
      mu  =. muj j } mu
      j   =. i2 * >: i.max <.@% i2 =. *:i
      mu  =. 0 j } mu
end.
   ix    =. i.max+1
   newmu =. (mu=ix) - (mu = -ix)
   newmu =. newmu - (*mu) * 0= newmu
1 (0) }newmu
)

NB - This function sets mu for 0 to be 1 - debatable!

(BTW,  Rosetta's current J proposal, 
   mu=: */@:-@~:@q:
doesn't work,  becaause of a change in the output of q: on an array - the right padding is
now 1s rather than 0s;  I forget how to get round the problem.)

But the J p: & q: verbs are pretty fast.   How do you suggest mu would help here?
Cliff Reiter and Richard Donovan both effectively select the maximum prime to append to
the sequence (in the sense of OEIS A080155) while I try to select the maximum number
of primes to include in the sequence.  Their approach allows prefetching a given number, n,
of primes with p: i. n which is going to be more efficient in J than using 4 p: ] for next prime. 
If one wants prime from 1 to 1000,  one could run }. mu >:1000 (as above) and then test all
_1 entries for primality,  but I don't see much point. 

Thanks,

Mike

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

Virus-free.www.avast.com

[Henry Rich]

mu=: */@:-@~:@q:

change to

mu=: */@:-@~:@q:"0

Henry Rich

[trx2358...@yahoo.com]

Whoops.  It seems I replied to the wrong thread.  I’ll just trust that interested parties are likely to read both.

Sent from Yahoo Mail for iPhone