Is it a lobster number?

Question

Introduction

A "lobster number", by my own designation, is a number that contains within itself all of its prime factors. The "lobster" description was inspired by the recent question "Speed of Lobsters". The basic idea is that each prime factor can be made by lobsters munching away digits of the number until you are left with just the factor.

Example: 51375 is a lobster number, since its prime factors are [3,5,137], which can be made by lobsters thusly: [**3**, 5**** / ****5, *137*]. Another lobster number is 62379, as the factors [3,29,239] can be formed as [**3**,*2**9,*23*9].

Challenge

Given a number as input, return whether it is a lobster number or not. Preferentially this is a boolean output, such as 1 or 0, or True or False.

Astute readers may realize that prime numbers are a trivial solution to this requirement, but since they don't allow the lobsters to eat any digits, they are out. Your program must not identify prime numbers as lobster numbers.

This is similar to OEIS A035140, but has the additional requirement that each digit of the factor must appear at least the same number of times in the number, and in the correct order. In other words, 132 is not a lobster number, since its factors are [2,3,11], and the 11 cannot be made by munching away at just 132. 312 is also not a lobster number, because its factors are [2,3,13], and 13 is out of order.

I believe the "mathematical" definition would be: "Determine if the number n is a composite number such that all prime factors of n are a subsequence of n".

Test Cases

59177  -> True
62379  -> True
7      -> False
121    -> True
187    -> False
312    -> False

As always, Standard Loopholes are forbidden.

Note:

It has come to my attention that the original reasoning I gave for not needing to handle 0 or 1 as input is faulty. However, requiring the proper output at this point would invalidate a number of answers. Therefore, let it hereby be known that neither 0 nor 1 are lobster numbers, but you also do not need to handle them as input (they are not valid test cases). If your code does handle them correctly, you may give yourself the Lobster Advocate Badge™.

Answer 1

Python 3, 155, 126, 124, 123, 120 116, 113 bytes

Yes! First python answer!

Saved 21 bytes due to a suggestion by Dominic van Essen to remove the for loop!

Saved 8 bytes because I realized I could use t*=True/False instead of t+=[True/False].

Saved another 2 bytes right after I finished editing because I realized t could simply be set to the same value as i and l!

Saved 1 byte based off Danis's python 2 comment.

Saved another 3 bytes based off Tipping Octopus's comment.

Saved another 4 bytes due to Tipping Octopus again!

Saved another 3 bytes thanks to Dominic's suggestion to remove the t variable.

New Answer

x=input()
n=int(x)
i=l=2
while~-n:
 if n%i:i+=1
 else:n//=i;l+=1;j=iter(x);l*=2*all(c in j for c in str(i))
print(l>4)

How it works

The while loop computes the prime factors of the input. If a prime factor is found, it checks if it is a subsequence of the input. l is multiplied by whether or not this is True. This takes advantage of the fact that python's True and False values act like 1s and 0s when you multiply by them. This means that instead of appending True/False to t and checking whether all(t) is True like in my old answer, I can just multiply l by 2*True/False and check its value in the print statement. The print statement prints True if l>4.

Try it online!

Old Answer

x=n=int(input())
l=[]
i=2
while i<=n:
 if n%i:i+=1
 else:n/=i;l+=[i]
t=[]
for p in l:i=iter(str(x));t+=[all(c in i for c in str(p))]
print(all(t)*len(l)>1)

Try it online!

Answer 2

Brachylog, 5 bytes

That's basically this: "Determine if the number n is a composite number such that all prime factors of n are a subsequence of n".

ḋṀ⊆ᵛ?

Try it online!

ḋṀ⊆ᵛ? (with implicit input n)
ḋ     get the prime factors of n
 Ṁ    they must be Ṁany (at least 2 to filter out primes)
  ⊆ᵛ  all of them must be an (ordered) subset of
    ? the input

Answer 3

Zsh -e -o glob_subst -o extended_glob, ⁴⁰ 38 bytes

>$1:
for i (`factor $1`)>${i///*}*~$i:

Try it online!

Outputs via exit code: 0 is a lobster number, 1 is not a lobster number

Explanation:

• > - do nothing, and send the output to:
  • $1: - the input with a : appended (e.g. 51375:). This is because factor outputs the input number itself, then a colon, then its factors, and we need to match based on that later.
• factor $1 - factorise the input (in the format 51375: 3 5 137)
• for i - for each element in the factorisation:
  • ${i} - take that element
  • ///* - prefix each character with a * (e.g. *1*3*7)
  • append *~ + the input + :
  • >, -o glob_subst - do nothing, and try to output to a file matching that pattern (there is only one file in the directory, the one we created earlier):
    • at this point the pattern is something like *1*3*7*~51375:
    • * - match zero or more characters; so *1*3*7* tests for a subsequence.
    • ~, -o extended_glob - the file must match *1*3*7* but not 51375: itself - this is to prevent prime numbers from being matched.
  • -e - exit immediately if there is an error (no files match that pattern) and set the exit code to 1. If all factors matched a file, there is no error and the exit code is 0.

Answer 4

05AB1E, 9 6 bytes

æ¨IfåP

Try it online! or Try all cases!

Commented:

æ          # get the powerset / all subsequences of the input
 ¨         # remove the last one (the input itself)
  If       # get all prime factors of the input
    å      # is each prime factor in the powerset?
     P     # take the product

Answer 5

Husk, 13 10 9 bytes

(Πm -> Λ simultaneously golfed-down by Razetime!)

Λo€hṖd¹dp

Try it online!

Returns 0 (falsy) for non-lobster numbers, and a positive nonzero integer (truthy) for lobster numbers.

How?

Λo       p    # is this true for each prime factor of input:
   €          # index (or zero if absent) of
        d     # its digits among
    hṖ        # all subsets (in order, without full set) of
      d¹      # digits of input

Answer 6

Python 2, 93 bytes

Outputs via exit code: 0 if it is a Lobster number, 1 otherwise.

n=m=input()
i=1
while~-m:
 i+=1
 while m%i<1:m/=reduce(lambda s,c:s[c==s[:1]:],`n`,`i`)or i%n

Try it online!

The algorithm for determining subsequences was borrowed from @xnor's answer to Is string X a subsequence of string Y?. A TypeError is raised when the subsequence check fails, and the i%n causes a ZeroDivisionError to occur on prime inputs.

Python 2, 92 bytes

One byte can be saved using exec, at the cost of segfaulting on large inputs.

n=m=input()
i=1
exec"i+=1\nwhile m%i<1:m/=reduce(lambda s,c:s[c==s[:1]:],`n`,`i`)or i%n\n"*n

Try it online!

Answer 7

Jelly, 10 bytes

DŒPḌḟiⱮÆfẠ

Try it online!

How it works

DŒPḌḟiⱮÆfẠ - Main link. Takes an integer n on the left
D          - Digits of n
 ŒP        - Powerset of the digits
   Ḍ       - Convert back to integers
    ḟ      - Remove n from this list
       Æf  - Yield the prime factors of n
      Ɱ    - Over each prime factor:
     i     -   Index of the factor in the powerset, or 0
         Ạ - All are true?

Answer 8

Retina 0.8.2, 95 bytes

.+
$*_¶$&
%O^$`.

+`^(__+?)(\1)*¶
$#2$*__¶$.1¶
_¶((.)+¶(?=(.+¶)*((?<-2>\2)|.)+$(?(2).))){2,}.+$

Try it online! Link includes test cases. Explanation:

.+
$*_¶$&

Duplicate the input, converting one copy to unary.

%O^$`.

Reverse both copies. (Reversing the unary copy has no effect, of course, other than being golfier.) Reversing the input allows it to be used for nondestructive subsequence matching (a simple subsequence matching Retina program works by destroying both strings on success).

+`^(__+?)(\1)*¶
$#2$*__¶$.1¶

Repeatedly extract the smallest proper (and therefore necessarily prime) factor of the unary input, until it is reduced to 1.

_¶((.)+¶(?=(.+¶)*((?<-2>\2)|.)+$(?(2).))){2,}.+$

Attempt to match the unary 1, followed by at least 2 factors, each of which can be matched against the reversed input by popping its previously captured characters as they are seen, followed by the reversed input.

Answer 9

Husk, 11 bytes

^{I got ninja'd..}

§&tΛo€Ṗd¹dp

Try it online!

Outputs truthy for a lobster number and falsy otherwise. This would be shorter if all returned 0 for empty lists.

Explanation

§&tΛo€Ṗd¹dp
          p prime factorization of the input
§           fork:
  t          is the list not composed of a single element?
 &          and,
   Λo    d   are all the prime factors' digits
     €       present in
      Ṗd¹    the powerset of the input's digits?

Answer 10

Haskell, 135 128 bytes

Saved 7 bytes thanks to @ovs!

f n=all(\x->x/=n&&(show n%show x))$foldl(\f x->[x|all((>0).mod x)f&&mod n x<1]++f)[][2..n]
(a:b)%(c:d)=b%([c|a/=c]++d)
_%x=x==[]

Try it online!

Answer 11

J, 27 bytes

1<[:*/](]#.@E.[-.-.)&":"+q:

Try it online!

Takes list of prime factors q: and original input, and for each pair, formats each as a string &":"+ and then applies the following verb in parens: ]#.@E.[-.-.

This verb set subtracts the factor digits from the input digits -. (leaving digits not in the factor) and then subtracts those from the input digits [-., leaving only input digits that are in factor, with order preserved.

We then check if the factor is a substring match of that E., which returns a boolean list of length input, with a 1 at any index where a match begins. Finally we interpret that as a base 2 number and convert to an integer #.@. This means that for a true result we need all factors to be greater than or equal to 1, and at least 1 factor to be greater than 1.

So we multiply all the results together [:*/ and check if that is greater than 1 1<.

Answer 12

Wolfram Language, 118 bytes

i|->Catch@AllTrue[MemberQ[a=FactorInteger@i,{i,_}]&&Throw@False;a,LongestCommonSequence@##==#&@@ToString/@{#[[1]],i}&]

Try it online!

Pure function; uses the |-> syntax, which is new in version 12.2. TIO is running version 12.0, so I've used Function FullForm there.

Test cases:

59177: expected True, got True
62379: expected True, got True
7: expected False, got False
121: expected True, got True
187: expected False, got False
312: expected False, got False

Answer 13

Pyth, 12 15 bytes

&!P_Q.A}Ry`Q`MP

Try it online!

-2 bytes by using ` instead of +k, +5 to account for primes needing to return false.

Answer 14

Python 2, 137 bytes

lambda n:(p(n)<1)*all(re.search('.*'.join(`d`),`n`)for d in range(2,n)if n%d<1and p(d))
p=lambda n:all(n%i for i in range(2,n))
import re

Try it online!

Answer 15

JavaScript (ES6),  80  79 bytes

Expects a string.

f=(n,m=n,k=2)=>n%k?k>n||f(n,m,k+1):m-k&&m.match([...k+''].join`.*`)&&f(n/k,m,k)

Try it online!

Commented

f = (              // f is a recursive function taking:
  n,               //   n = initially the input as a string,
                   //       then an integer
  m = n,           //   m = copy of the input
  k = 2            //   k = current divisor candidate
) =>               //
  n % k ?          // if k is not a divisor of n:
    k > n ||       //   stop the recursion if k > n
    f(n, m, k + 1) //   otherwise: do a recursive call with k + 1
  :                // else:
    m - k &&       //   if k is not equal to m
    m.match(       //   and we can find in m:
      [...k + '']  //     the digits of k in the correct order
      .join`.*`    //     possibly with other digits in between
    ) &&           //   then:
    f(n / k, m, k) //     do a recursive call with n / k

Answer 16

C (gcc), 264 236 219 bytes

-45 bytes thanks to ceilingcat!

i,j,k,b,n,r,z;char p[9],c[6];l(int*s){b=1;for(j=k=!strcpy(c,s);p[j]*b;j++)for(b=0;c[k]&&(c[k]==p[j]?c[k]=5,b=1,0:1);k++);b=b;}f(int*s){r=1;n=z=atoi(s);for(i=2;n>1;i++)for(;sprintf(p,"%d",i),n%i<1;n/=i)r&=i-z&&l(s);b=r;}

Try it online!

But it's a shame that C needs all those bytes. I believe that a better approach could be found, so here is an ungolfed and highly commented version that you can use to get yourself into the problem and hopefully develop something better.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// indexes
int i,j,k;

// int copy of the input s, used to find prime factors
int n;

// array to store char* copy of the prime factors of n
char p[20];

// bool telling whether a particular digit of p
// has been successfully "lobsted" in s
int b;

// checks whether a given factor p "lobsters" s
int l(char*s)
{
    // just copy of s, so that we can preserve the input
    // to check whether the next factors "lobster" it or not
    char c[6];
    
    strcpy(c,s);
    
    // we don't do it at the start of the k-loop
    // because we want to continue the loop from
    // where we left it. 31 do not "lobster" 12345.
    // After checking for 3, we don't check for 1 from the beginning
    k = 0;
    
    // until p has digits to check for lobsterness
    for(j=0;p[j];j++) {
        
        // assume the digit can't be lobsted in c
        b = 0;
        
        // untill c has digit that could potentially
        // "lobster" the digit of p
        for(;c[k];k++) {
            
            // if the digit of p double equals one of the digits of c
            if(p[j]==c[k]) {
                
                c[k] = '*'; // delete the digit of c
                b = 1; // set "lobsted" to true
                break;
            }
        }
        
        // if a digit couldn't be lobsted
        if(!b) break;
    }
    
    // return 0 if at least one digit couldn't be lobsted,
    // return 1 if all of them were sucessfully lobsted
    return b;
}

// find factors of s and launch l() for each factor found
int f(char*s)
{
    // n is, initially, the int copy of the input
    n = atoi(s);
    
    // until a factor can be found in n
    for(i=2;n>1;i++) {
    
        // if i is a factor of n
        if( !(n%i) ) {
            
            // if the first factor found is the original number
            if(i==atoi(s)) return 0;
        
            // until i divides n, divide n by i
            for(;!(n%i);n/=i);
            
            // make a char[] copy of the factor i, named p
            sprintf(p,"%d",i);
            
            // if p doesn't "lobster" s
            if(!l(s)) return 0;
        }
    }
    
    // reachable only if each factor p "lobsted" the original number s
    return 1;
}


int main() {

    char test[6][6] = {
        "59177",
        "62379",
        "7",
        "121",
        "187",
        "312" };
    
    for(int t = 0; t < 6; t++) {
        
        printf("%s", test[t]);
        
        for(int dots = 0; dots < 8-strlen(test[t]); dots++) {
            
            printf(".");
        }
        
        printf("%d\n\n", f(test[t]));
        
        memset(p,0,20);
    }
    
    return 0;
}

And in case you want to golf from here, rather than start a new approach, here is the same code without comments

Answer 17

PowerShell Core, 126 bytes

param($n)(($u=2..($n-1)|?{!($n%($a=$_)-or(2..($a-1)|?{!($a%$_)}))})|?{$n-match(("$_"|% t*y)-join'.*')}).Count-eq$u.count-and$u

Try it online!

Takes an integer and returns a boolean

($u=2..($n-1)|?{!($n%($a=$_)        # finds the factors of the input
-or(2..($a-1)|?{!($a%$_)}))})       # keep them only if they are prime
|?{$n-match(("$_"|% t*y)-join'.*')} # add a .* between each digits of each prime factors and check if they match the input
.Count-eq$u.count-and$u             # Check that the input has factors and that they all match the input