17
\$\begingroup\$

\$723 = 3 \times 241\$ is a semi-prime (the product of two primes) whose prime factors include all digits from \$1\$ to \$n\$, where \$n\$ is the total number of digits between them. Another way to look at this is that the (sorted) digits in the factorisation of \$723\$ are all consecutive. The first 10 such semi-primes and their factorisations are

[26, 62, 723, 862, 943, 1263, 2906, 3086, 7082, 7115]
[2×13, 2×31, 3×241, 2×431, 23×41, 3×421, 2×1453, 2×1543, 2×3541, 5×1423]

We will call the numbers that have this feature all-inclusive semi-primes

You may choose whether to:

  • Take an integer \$n\$ and output the \$n\$th all-inclusive semi-prime (0 or 1 indexed)
  • Take an integer \$n\$ and output the first \$n\$ all-inclusive semi-primes
  • Output the sequence of all-inclusive semi-primes indefinitely

This is so the shortest code in bytes wins!

This is a Jelly program which takes an integer \$n\$ and outputs the first \$n\$ all-inclusive semi-primes and their factorisations. Spoilers for any Jelly based solutions.

The first 100 all-inclusive semi-primes are

[26, 62, 723, 862, 943, 1263, 2906, 3086, 7082, 7115, 8306, 9026, 10715, 10793, 10826, 10862, 11705, 12443, 12773, 21155, 21443, 22313, 22403, 29126, 29306, 31286, 32906, 69302, 70922, 72902, 73082, 87302, 90722, 91226, 91262, 92306, 92702, 104903, 106973, 108326, 108722, 109262, 112862, 116213, 123086, 123155, 127082, 128306, 129026, 129743, 130826, 132155, 135683, 142283, 148373, 155123, 157373, 161393, 171305, 181205, 206315, 216305, 225833, 226223, 230543, 237023, 241103, 241223, 244913, 259433, 270934, 271294, 273094, 274913, 275903, 280403, 287134, 291274, 310715, 312694, 312874, 316205, 317105, 320615, 321155, 328714, 330874, 335003, 335086, 335243, 337111, 340313, 349306, 350926, 355741, 359881, 373701, 379371, 379641, 380581]
\$\endgroup\$
9
  • 2
    \$\begingroup\$ @Shaggy Fraid that's a bit too much of a stretch, sorry \$\endgroup\$ Nov 12 '20 at 16:10
  • 4
    \$\begingroup\$ Since there are only 9 possible digits for the primes, this is a finite sequence. If we choose to output all all-inclusive semi-primes, do we need to keep the order? \$\endgroup\$
    – ovs
    Nov 12 '20 at 17:20
  • 4
    \$\begingroup\$ @ovs I didn't realise it was finite. In that case, yeah, you may output the entire sequence in any order, but the \$n\$th term based options must still use ascending order (my guess is that ignoring order just saves bytes from avoiding sorting?) \$\endgroup\$ Nov 12 '20 at 17:22
  • 7
    \$\begingroup\$ The last term is \$842696243 = 8641 \times 97523\$. \$\endgroup\$
    – Arnauld
    Nov 12 '20 at 17:37
  • 3
    \$\begingroup\$ @GregMartin \$943 = 23\times41\$ \$\endgroup\$ Nov 13 '20 at 11:21

13 Answers 13

9
\$\begingroup\$

05AB1E, 17 16 14 12 11 bytes

∞ʒÒDS{āQиg<

Outputs the infinite sequence.

-2 bytes thanks to @CommandMaster, which also opened up the opportunity to golf 2 more bytes
-1 byte thanks to @ovs.

Try it online.

Explanation:

∞         # Push an infinite list of positive integers: [1,2,3,...]
 ʒ        # Filter this list by:
  Ò       #  Get a list of its prime factors (including duplicates)
   D      #  Duplicate this list
    S     #  Convert the list of integers to a flattened list of digits
     {    #  Sort these digits
      ā   #  Push a list in the range [1,length] (without popping the list itself)
       Q  #  Check that the two lists are equal (1 if truthy; 0 if falsey)
    и     #  Repeat the list if prime factors that many times as list
          #  (so it'll become empty for falsey results; and stays the same for truthy)
     g    #  Pop and push the length of this list
      <   #  And decrease it by 1
          #  (NOTE: only 1 is truthy in 05AB1E, so if the amount of prime factors was
          #  anything other than 2, this will be falsey)
          # (after which the filtered infinite list is output implicitly as result)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 14 bytes: ∞ʒÒ©g<∞®J{SÅ?* though I feel like at least one byte can be removed \$\endgroup\$ Nov 12 '20 at 18:45
  • \$\begingroup\$ @CommandMaster Ah nice! Didn't think about using Òg instead of fg like that. And using the approach of ®S{āQ of my existing answer instead of your ∞®J{SÅ? saves 2 more bytes, so thanks for -4. :) \$\endgroup\$ Nov 12 '20 at 18:55
  • 1
    \$\begingroup\$ ∞ʒÒDS{āQиg< for 11 bytes. \$\endgroup\$
    – ovs
    Nov 12 '20 at 19:14
  • \$\begingroup\$ @ovs Thanks! Smart little golf. \$\endgroup\$ Nov 12 '20 at 19:33
8
\$\begingroup\$

Brachylog, 9 bytes

-3 thanks to Unrelated String!

This defines a predicate that unifies with all-inclusive-semi-primes. In Prolog this is equivalent to a generator, that will return all all-inclusive-semi-primes one by one.

ḋĊcẹo~⟦₁&

Try it online!

ḋĊcẹo~⟦₁&
ḋ         prime factors
 Ċ        are a pair (list of length 2)
  cẹ      and the elements of the concatenation (all the digits)
    o     ordered
     ~⟦₁  are the result of a range operation, f.e.
            4 ⟦₁ [1,2,3,4]
            [1,2,3,4] ~⟦₁ 4
        & return the input
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Just about exactly what I was on the verge of posting, except I don't think you need the ℕ₁ᵐ since ⟦₁ is a range from 1 anyhow. \$\endgroup\$ Nov 12 '20 at 17:12
  • 1
    \$\begingroup\$ @UnrelatedString Ah, of course, thanks! (And sorry for stealing the Brachylog answer here. :-)) \$\endgroup\$
    – xash
    Nov 12 '20 at 17:18
  • 1
    \$\begingroup\$ I did stick a d in there so it would have taken at least another minute or two to realize that's a problem. Plus, having competition means I actually have to up my game ;) \$\endgroup\$ Nov 12 '20 at 17:26
  • \$\begingroup\$ I'm new here, but why don't you need to include the header in the bytecount? The code just outputs true. without the header \$\endgroup\$
    – bRost03
    Nov 16 '20 at 15:22
  • 1
    \$\begingroup\$ @bRost03 Prolog's IO is a bit strange. true. indicates that the predicate can unify with something. To get a result, you must name an output variable: TIO. If you'd run this locally, you could either stop the search . or search for more results ,. So this is a generator predicate, which is allowed for the [sequence] tag. More generally: usually on CG, functions are accepted that handle IO per function arguments – you don't have to build complete programs. \$\endgroup\$
    – xash
    Nov 16 '20 at 17:55
6
\$\begingroup\$

05AB1E, 13 bytes

Outputs all all-inclusive semi-primes, not quite in ascending order.

7°ÅpâʒS{āQ}PÙ

Try it online!

Commented:

The S{āQ is borrowed from Kevin's answer.

7°              # push 10^7
  Åp            # push the first 10^7 primes
                # the first 5694505 would be enough but costs more bytes
    â           # take the cartesian product of that list with itself
                # to create all pairs of primes
     ʒ    }     # filter the pairs by
      S         #   split into a list of digits
       {        #   sort the digits
        ā       #   push the range [1 .. length]
         Q      #   are those lists equal?
           P    # take the product of each pair
            Ù   # take the unique elements

The different order is a result of the order of the cartesian product, pairs that start with 2 are first, then pairs with 3, 7... The order could be fixed by replacing Ù with ê (unique sort), but this would prevent output until all calculations are finished.

98765431, the 5694505th prime number, is the largest prime that can be used to create an all-inclusive semi-prime.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You could use ê for your submission to conform to the spec and just replace it with Ù in your TIO so it runs faster. \$\endgroup\$
    – Shaggy
    Nov 12 '20 at 18:30
  • \$\begingroup\$ @Shaggy I guess it hasn't been added to the post yet, but caird clarified in the comments that for this output method we can use a different order. And since the current version runs better and produces any output on TIO I will keep it like this. \$\endgroup\$
    – ovs
    Nov 12 '20 at 18:35
5
\$\begingroup\$

Stax, 22 21 17 16 bytes

âH«q☻╧Ñ♦├x╓║Nm"°

Run and debug it

-1 byte using a generating block.

-4 bytes using a filter.

-1 byte from wastl.

Outputs infinite list, separated by newlines.

Explanation (Uncompressed)

VIf|fY%2=y$eEc%R|}*
VIf                          filter natural numbers, printing truthy values 
                             take current iteration value
    |fY                      store prime factorization in Y(without pop)
       %                     Length   
        2=                   Equals 2?
          y                  Push prime factors again
           $eE               Convert to string, then to digits
              c%             copy and take length
                R            Range [1..length]
                 |}          are they setwise equal?
                   *         multiply the two values
\$\endgroup\$
1
5
\$\begingroup\$

Husk, 21 19 18 16 14 bytes

(or 15 bytes for versions that just output the n-th, or first n all-inclusive semi-primes, and so will always terminate instead of running indefinitely)

Edit: -2 bytes thanks to Razetime's suggestion to just use p twice instead of my complicated approach of spending 3 bytes just to save one character...

...then another -1 byte, and again -3 bytes, thanks to Razetime

...then -2 more bytes thanks to Leo

fȯεtpfȯS¦ŀṁdpN

Try it online!

Returns infinite list of all-inclusive semi-primes.
TIO header selects first 20 to avoid timing-out.

!fo§&o=2L(§=OoḣLṁd)pN
!                       # get the input-th element of
 f                  N   # natural numbers that satisfy
  o§&              p    # both conditions of prime factors:
     o=2L               # there are 2 of them, and
                ṁd)     # their digits
            O           # sorted
         (§=            # are equal to
             oḣL        # the sequence from 1..number of digits
\$\endgroup\$
15
  • \$\begingroup\$ Shorter without combinators(and indexing) \$\endgroup\$
    – Razetime
    Nov 12 '20 at 15:49
  • \$\begingroup\$ Yes! Shorter, and also much less complicated! Thanks! \$\endgroup\$ Nov 12 '20 at 15:54
  • \$\begingroup\$ Why not remove indexing? \$\endgroup\$
    – Razetime
    Nov 12 '20 at 15:56
  • 1
    \$\begingroup\$ @JoKing - Luckily output option 2 only costs +1 byte, so terminating-version now added as an alternative solution. \$\endgroup\$ Nov 15 '20 at 13:14
  • 1
    \$\begingroup\$ =2L can become εt, and using ¦ (set inclusion) instead of = (list equality) saves you from having to sort the list Try it online! \$\endgroup\$
    – Leo
    Nov 16 '20 at 0:37
4
\$\begingroup\$

Japt, 22 21 19 bytes

Returns the first n terms; replace j with i to return the 0-indexed nth term.

È=k)cì ÍeX¬ÊõXÊÉ}jU

Try the first 10 terms or the first 100 terms

È=k)cì ÍeX¬ÊõXÊÉ}jU     :Implicit input of integer U
È                       :Function taking an integer X as argument
 =                      :  Reassign to X
  k                     :  Prime factors
   )                    :  End reassignment
    c                   :  Flat map
     ì                  :    Digit arrays
       Í                :  Sort
        e               :  Test equality with
         X¬             :    Join X
           Ê            :    Length (a)
             XÊÉ        :    Length of X minus 1 (b)
            õ           :    Range [b,a]
                }       :End function
                 jU     :Get the first U integers that return true (or the Uth, if using i)
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 108 bytes

Returns the n-th term, 1-indexed.

f=(n,k=2)=>(g=n=>a=q>n?'':n%q?g(n,q++):q+g(n/q,i--))(k,q=i=2)*i|[...a].sort().some(v=>v^++i)||--n?f(n,k+1):k

Try it online!

Commented

f = (                   // f is a recursive function taking:
  n,                    //   n = input
  k = 2                 //   k = next integer to test
) => (                  //
  g = n =>              // g is a recursive function taking an integer and building
                        // a concatenation of its divisors
    a =                 //   assign the final result to a:
      q > n ?           //     if q is greater than n:
        ''              //       stop and coerce the answer to a string
      :                 //     else:
        n % q ?         //       if q is not a divisor of n:
          g(n, q++)     //         do a recursive call to g with q + 1
        :               //       else:
          q +           //         append q
          g(n / q, i--) //         and do a recursive call to g with n / q and i - 1
)(k, q = i = 2)         // initial call to g with n = k, q = 2 and i = 2
* i |                   // if i is not equal to 0 (i.e. k has not exactly 2 divisors)
[...a].sort()           // or the sorted digits of a ...
.some(v => v ^ ++i)     // ... do not match the sequence 1, 2, ..., x
|| --n ?                // or the previous conditions are met but decrementing n does
                        // not result in 0:
  f(n, k + 1)           //   do a recursive call to f with k + 1
:                       // else:
  k                     //   success: return k
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 123 bytes

outputs the nth term

(n=w=0;While[n<#,If[Last/@(f=FactorInteger)@w=={1,1}&&(s=Sort[Join@@(IntegerDigits@#&@@@f@w)])==Range@Max@s,n++];w++];w-1)&

Try it online!

the following prints all 36918 terms

Wolfram Language (Mathematica), 139 bytes

Union@(f=Flatten)[Times@@d/@#&/@Select[f[(q=#;TakeDrop[q,#]&/@o)&/@Permutations[o=Range@#],1],And@@PrimeQ[(d=FromDigits)/@#]&]&/@3~Range~9]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Factor, 190 175 bytes

: f ( n -- n ) 1 [ over 0 = ] [ dup factors [ 10 >base ] map
[ pair? ] [ concat [ length [1,b] [ 48 + ] map ] keep
diff ""= ] bi and [ [ 1 - ] dip ] when 1 + ] until nip 1 - ;

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Do you have a rationale for excluding the USING: statement (aka library imports) from byte count? (Not that I want to disadvantage an already verbose language even more) \$\endgroup\$
    – Bubbler
    Nov 19 '20 at 6:33
  • \$\begingroup\$ @Bubbler I'm not sure at all what I do is right. My explanation is that all words in Factor live in vocabularies - for example the stack shuffling words like swap reside in kernel vocabulary. Thus I would need to add to the byte count all imports, as well as the IN: export. \$\endgroup\$ Nov 19 '20 at 7:37
  • \$\begingroup\$ After further investigation, it looks like cat started the tradition of auto-use (relevant doc), which can be toggled in the interactive UI, or enabled for running scripts via .factor-rc file. Maybe I should ask in meta. \$\endgroup\$
    – Bubbler
    Nov 19 '20 at 9:50
  • \$\begingroup\$ @Bubbler Thank you for your investigation! What do you think about using quotations (lambdas) - as in cat's answer - instead of words, defined with a stack effect : f ( n -- n ) ? \$\endgroup\$ Nov 19 '20 at 10:22
  • 1
    \$\begingroup\$ Anonymous lambdas look fine to me, as it's pushed to stack on definition and can be called and reused. \$\endgroup\$
    – Bubbler
    Nov 19 '20 at 10:24
2
\$\begingroup\$

Java (JDK), 228...214 212 bytes

-7 bytes thanks to @Kevin Cruijssen!

b->{int x=9,l,C[],y,i=b;for(;i>0;i-=b){y=++x;var s="";for(b=0;y>1&&b++<2;y/=l,s+=l)for(l=1;l++<y&y%l>0;);C=new int[l=s.length()];b-=y;for(var c:s.getBytes())b&=c-49<l&c>48?C[c-49]=1:0;for(int k:C)b&=k;}return x;}

Try it online!

Returns the nth element of the sequence (1-indexed).

Ungolfed:

b -> {
int x = 9, l, C[], y, b, i = b;
for (; i > 0; i -= b) {
    y = ++x;
    var s = "";
    for (b = 0; y > 1 && b++ < 2; y /= l, s += l)
        for (l = 1; l++ < y & y % l > 0;);
    C = new int[l = s.length()];
    b -= y;
    for (var c : s.getBytes()) 
      b &= c - 49 < l & c > 48 ? C[c - 49] = 1 : 0;
    for (int k : C) b &= k;
}
return x;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 221 bytes. y/=d,s+=d inside the loop so you can ditch the {}; .toCharArray() to .getBytes(); & you don't need to count the trailing ; of lambdas \$\endgroup\$ Nov 12 '20 at 18:25
  • \$\begingroup\$ @KevinCruijssen Nice, thanks! \$\endgroup\$
    – rues
    Nov 12 '20 at 18:27
1
\$\begingroup\$

Retina, 112 111 bytes


123456789
L$`.
:::$>`
+%/\d$/&Lv$`(.)(.*:)(.)
$`$1$3$2$'
\d+
*
A`:_?:|(:_+)\1|:(__+)\2+:
:(_+):(_+):
$.($.1*$2

Try it online! Above program outputs the entire sequence, but TIO times out if the total number of semiprime digits is not less than 5, so the link only outputs six elements. Explanation:


123456789

Start with the potential semiprime digits.

L$`.
:::$>`

Get all their prefixes and add some markers to delimit the potential prime factors.

+%/\d$/&Lv$`(.)(.*:)(.)
$`$1$3$2$'

Generate all permutations of the digits among the potential primes.

\d+
*

Convert all the numbers to unary.

A`:_?:|(:_+)\1|:(__+)\2+:

Delete all results unless both numbers are prime and the first is greater than the second. This is one of the slowest parts of the program; Try it online! can calculate 23 results if these are split into separate filters. However, despite my best efforts, larger results are simply too slow.

:(_+):(_+):
$.($.1*$2

Calculate the resulting semiprimes.

\$\endgroup\$
1
\$\begingroup\$

Raku, 123 bytes

{grep({$!=$_/($/=first $_%%*,2..$_);$!.is-prime&&{.[0]===.first(:k,0)}(+«[\∖]
"$!$/".comb.Bag,|('1'..'9'))},9..∞)[$_]}

Try it online!

  • $_ is the argument to the function.
  • grep(..., 9..∞) filters the integers from nine to infinity. [$_] indexes into that sequence with the function argument and returns that value. Within the filtering function $_ is the number being tested.
  • $! = $_ / ($/ = first $_ %% *, 2..$_) sets $/ to the smallest (necessarily prime) divisor of $_, and $! to $_ divided by that number.
  • If $! is not prime, then $_ is not a semiprime, so the filter function returns false.
  • "$!$/" is the concatenation of the semiprime's two factors.
  • .comb returns a list of those digits.
  • .Bag returns a bag (that is, a set with multiplicity) of those digits.
  • [\∖] is a triangular reduction using the set-difference operator on the list consisting of the aforementioned Bag and each of the digits from 1 to 9. The elements of this reduction are the initial Bag, then the same bag with a single 1 removed, then that second Bag with a single 2 removed, and so on.

Now the idea is to check that this sequence of bags gets exactly one element smaller as one of each successive digit is removed until it reaches a size of zero.

  • turns that list of Bags into a list of their sizes (which counts multiplicity).
  • That list of sizes is fed into the bracket-delimited anonymous function, which is immediately called. Within that function, $_ refers to the list of sizes.
  • .first(:k, 0) returns the index of the first zero element of the list. If no element is zero, Nil is returned instead.
  • .[0] === .first(:k, 0) is true if the index of the first zero is equal to the first element of the list. This will be true only for lists of the form N, N-1, N-2, ..., 1, 0, 0, 0. From the way the list is constructed, each successive element can only ever be one or zero less than the preceding element.
\$\endgroup\$
0
\$\begingroup\$

Python 3.8, 208 bytes

def f(x,r={26},n=9,R=range):
 while len(r)<x:
  for d in R(2,n:=n+1):n%d<1and all(k%i for k in(d,n//d)for i in R(2,k))*(l:=[*map(int,sorted(str(d)+str(n//d)))])==[*R(1,len(l)+1)]and r.add(n)
 return sorted(r)

Try it online!

Inputs an integer \$n\$ and output the first \$n\$ all-inclusive semi-primes (\$1\$-indexed).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.