16
\$\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\$
  • 2
    \$\begingroup\$ @Shaggy Fraid that's a bit too much of a stretch, sorry \$\endgroup\$ – caird coinheringaahing Nov 12 at 16:10
  • 3
    \$\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 at 17:20
  • 3
    \$\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\$ – caird coinheringaahing Nov 12 at 17:22
  • 6
    \$\begingroup\$ The last term is \$842696243 = 8641 \times 97523\$. \$\endgroup\$ – Arnauld Nov 12 at 17:37
  • 3
    \$\begingroup\$ @GregMartin \$943 = 23\times41\$ \$\endgroup\$ – caird coinheringaahing Nov 13 at 11:21

13 Answers 13

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
| improve this answer | |
\$\endgroup\$
  • 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\$ – Unrelated String Nov 12 at 17:12
  • 1
    \$\begingroup\$ @UnrelatedString Ah, of course, thanks! (And sorry for stealing the Brachylog answer here. :-)) \$\endgroup\$ – xash Nov 12 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\$ – Unrelated String Nov 12 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 at 15:22
  • \$\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 at 17:55
8
\$\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)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 14 bytes: ∞ʒÒ©g<∞®J{SÅ?* though I feel like at least one byte can be removed \$\endgroup\$ – Command Master Nov 12 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\$ – Kevin Cruijssen Nov 12 at 18:55
  • 1
    \$\begingroup\$ ∞ʒÒDS{āQиg< for 11 bytes. \$\endgroup\$ – ovs Nov 12 at 19:14
  • \$\begingroup\$ @ovs Thanks! Smart little golf. \$\endgroup\$ – Kevin Cruijssen Nov 12 at 19:33
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.

| improve this answer | |
\$\endgroup\$
  • 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 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 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
| improve this answer | |
\$\endgroup\$
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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Shorter without combinators(and indexing) \$\endgroup\$ – Razetime Nov 12 at 15:49
  • \$\begingroup\$ Yes! Shorter, and also much less complicated! Thanks! \$\endgroup\$ – Dominic van Essen Nov 12 at 15:54
  • \$\begingroup\$ Why not remove indexing? \$\endgroup\$ – Razetime Nov 12 at 15:56
  • 1
    \$\begingroup\$ @JoKing - Luckily output option 2 only costs +1 byte, so terminating-version now added as an alternative solution. \$\endgroup\$ – Dominic van Essen Nov 15 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 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)
| improve this answer | |
\$\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
| improve this answer | |
\$\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!

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
  • \$\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 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\$ – Galen Ivanov Nov 19 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 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\$ – Galen Ivanov Nov 19 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 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;
}
| improve this answer | |
\$\endgroup\$
  • 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\$ – Kevin Cruijssen Nov 12 at 18:25
  • \$\begingroup\$ @KevinCruijssen Nice, thanks! \$\endgroup\$ – user Nov 12 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.

| improve this answer | |
\$\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.
| improve this answer | |
\$\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).

| improve this answer | |
\$\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.