32
\$\begingroup\$

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™.

\$\endgroup\$
16

16 Answers 16

15
\$\begingroup\$

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!

\$\endgroup\$
12
  • 2
    \$\begingroup\$ Nice work! It seems to me that the for loop might be redundant, and that everything it does could be transferred to the while loop, something like [this](tio.run/##HY1BCsJADEX3c4pshIldSC1SnBovUroQmdKUkJZpxHr60XH3H@/… ) (note that I don't really know Python, so there are probably some howlers in my tinkering...) \$\endgroup\$ – Dominic van Essen Jan 24 at 23:27
  • \$\begingroup\$ Beat me to it, with a better answer to boot! I'll see if I can trim mine down at all... \$\endgroup\$ – IronEagle Jan 24 at 23:32
  • 4
    \$\begingroup\$ The iter trick to check subsequences is really cool! I've been golfing in Python for years and had never seen it or had it occur to me. \$\endgroup\$ – xnor Jan 25 at 19:49
  • 1
    \$\begingroup\$ @xnor Tbh, I saw it on a stack overflow post. \$\endgroup\$ – qwatry Jan 25 at 21:18
  • 1
    \$\begingroup\$ @pxeger l<<= almost works. It works correctly for all the lobster numbers, but it I think if a number has at least 2 factors (or a double factor) that are subsequences, it will incorrectly identify them as lobster numbers. It might work if I changed the truthy check in the print function, but I can't think of an obvious way to do it that would still save bytes. \$\endgroup\$ – qwatry May 16 at 23:24
14
\$\begingroup\$

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
\$\endgroup\$
2
8
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

Zsh -e -o glob_subst -o extended_glob, 40 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.
\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use all here for -1: Try it online! \$\endgroup\$ – Razetime Jan 24 at 15:49
  • 1
    \$\begingroup\$ I was already typing-in that improvement while your comment arrived! Thanks (and credit for the simultaneous improvement)! \$\endgroup\$ – Dominic van Essen Jan 24 at 15:54
5
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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?
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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?
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 128 bytes by combining two lines from the definition of (%). \$\endgroup\$ – ovs Jan 25 at 22:27
  • \$\begingroup\$ @ovs Nice, thanks! \$\endgroup\$ – user Jan 25 at 22:57
3
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf! This is a nice first answer! Here are tips for golfing in Mathematica (I'm not sure if it's the same as Wolfram Language). \$\endgroup\$ – user Jan 26 at 19:01
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This returns 'True' for prime numbers, which is not allowed. \$\endgroup\$ – Manish Kundu Jan 25 at 8:58
2
\$\begingroup\$

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!

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

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
\$\endgroup\$
2
\$\begingroup\$

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<.

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

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

\$\endgroup\$
2
  • \$\begingroup\$ @ceilingcat thank you! \$\endgroup\$ – Sheik Yerbouti Jan 27 at 10:30
  • \$\begingroup\$ @ceilingcat thank you again! You should change your name in golfingcat :D \$\endgroup\$ – Sheik Yerbouti Feb 14 at 12:19

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.