7
\$\begingroup\$

Input

An integer k composed of 1 and 2, with at least 3 digits and at most 200 digits.

Output

Another integer k' obtained by removing at most one (could be none) digit from k, such that k' is composite, and then another integer p for a non-trivial (that is, not 1 or k') factor of k'.

Test Cases

121212 -> 121212 10101
11121 -> 1112 506
12211 -> 2211 201
2122121211212 -> 2122121211212 2
212221112112211 -> 21221112112211 4933994911

Assume that there is always a valid output.

\$\endgroup\$
6
  • \$\begingroup\$ shouldnt that say k' is formed by removing at least 1 digit? also are you looking for just any factor of k' \$\endgroup\$
    – pacman256
    Jan 21 at 16:33
  • \$\begingroup\$ any (non-trivial) factor. and no, it is at most one digit \$\endgroup\$
    – Sunny Lu
    Jan 21 at 16:35
  • 5
    \$\begingroup\$ Proof that it's always possible: For all 1 or 2, remove one digit if odd number of digits, then it's always 11x10101; Otherwise, one of keep, remove a 1, and remove a 2 result 0 modulo 3 \$\endgroup\$
    – l4m2
    Jan 21 at 18:21
  • 1
    \$\begingroup\$ @l4m2 Edge case 111 falls under 0 modulo 3 case. \$\endgroup\$
    – Neil
    Jan 21 at 20:03
  • \$\begingroup\$ The second test case 11121 is wrong, it’s already a composite number so no digit should be removed. \$\endgroup\$
    – Fatalize
    Jan 22 at 10:49

10 Answers 10

4
\$\begingroup\$

Jelly,  15  13 bytes

DŒPḌẒÐḟṪÆḌṪṭƊ

A monadic Link that accepts an integer, k, and yields a pair of integers, [k', p].

Try it online!

How?

Creates the powerset of ks digits to look for candidates for k'. Jelly produces powersets that are sorted by length, so k will be at the right and all other valid k' candidates to the right of any other junk.

The code then takes, as k', the rightmost that is not prime (due to length this is also composite), which will either be k or k less one of its digits. It then tacks on the largest proper divisor of this, p.

DŒPḌẒÐḟṪÆḌṪṭƊ - Link: integer, k         e.g. 212
D             - decimal digits {k}            [2,1,2]
 ŒP           - powerset                      [[],[2],[1],[2],[2,1],[2,2],[1,2],[2,1,2]]
   Ḍ          - convert from decimal digits   [0,2,1,2,21,22,12,212]
     Ðḟ       - discard those for which:
    Ẓ         -   is prime?                   [0,1,21,22,12,212]
       Ṫ      - tail                          212
            Ɗ - last three links as a monad - f(k'=that):
        ÆḌ    -   proper divisors of k'       [1,2,4,53,106]
          Ṫ   -   tail                        106
           ṭ  -   tack to k'                  [212,106]
\$\endgroup\$
4
\$\begingroup\$

Vyxal 3, 12 bytes

ι*J⌊ᵐϩṄ¬:ḟh;

Try it Online!

Outputs largest possible k' and the first prime factor. Takes input as a string

Explained

ι*J⌊ᵐϩṄ¬:ḟh;­⁡​‎‎⁡⁠⁡‏⁠‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌­
ι             # ‎⁡Range 0 -> len input
 *            # ‎⁢And to each index, remove the letter at that position in the input
  J           # ‎⁣Add the input to that list so the unaltered input is an option
   ⌊          # ‎⁤Convert each to int
    ᵐϩ        # ‎⁢⁡Get the maximum by
      Ṅ¬      # ‎⁢⁢Not a prime
        :ḟ    # ‎⁢⁣Push a list of prime factors of that without popping
          h;  # ‎⁢⁤And pair the first of those with k'
💎

Created with the help of Luminespire.

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

Brachylog, 7 bytes

⊇PḋṀh;P

Try it online!

Outputs a list with the factor p first, and k' second.

Explanation

Since it’s been proven in a comment that it’s always possible for any input, we can state that P is a subset of the input without specifying the number of digits to remove. Since will try the biggest subsets first (including the original input), it will succeed with at most 1 digit removed.

⊇P         P is an integer which is a subset of the input integer
  PḋṀ      P has Ṁany prime ḋivisors (at least 2, so P is composite)
    Ṁh;P   Output = [First prime divisor of P, P]
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 26 bytes

I⮌⌈EIE³Φθ⁻μ⌕θIι⟦⌈Φι∧λ¬﹪ιλι

Try it online! Link is to verbose version of code. Explanation: Just tries removing one 1 and one 2 since by @l4m2's comment at least one of the two or three numbers will be composite. (Removing every possible digit turns out to take the same length but it will of course be slower.)

      ³                     Literal integer `3`
     E                      Map over implicit range
        θ                   Input as a string
       Φ                    Filtered where
          μ                 Current index
         ⁻                  Does not equal
           ⌕                Index of
              ι             Outer value
             I              Cast to string
            θ               In input string
    I                       Cast to integer
   E                        Map over values
                  ι         Current value
                 Φ          Filter on implicit range
                    λ       Inner value
                   ∧        Logical And
                       ι    Outer value
                     ¬﹪     Is divisible by
                        λ   Inner value
                ⌈           Take the maximum
                         ι  Current value
               ⟦            Make into list
  ⌈                         Take the maximum
 ⮌                          Reversed
I                           Cast to string
                            Implicitly print

31 bytes for a very fast version which only looks for factors below 12 (except for 11 itself, which is a special case):

I⮌⌈EIE³Φθ⁻μ⌕θIι⟦⌈Φ⌊⟦¹²ι⟧∧λ¬﹪ιλι

Try it online! Link is to verbose version of code.

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

JavaScript (ES11), 60 bytes

Similar to l4m2's strategy, but we first test whether \$11\$ is a divisor of either \$n\$ or \$\lfloor n/10\rfloor\$ before considering removing a digit according to \$n\bmod 3\$.

Expects a BigInt and returns "k',p" as a comma-separated string.

n=>(x=n)%11n&&(x/=10n)%11n?`${n},3`.replace(n%3n,""):x+[,11]

Try it online!


JavaScript (ES6), 51 bytes

A more limited version without BigInts. This time we first attempt to remove a digit and move to \$p=11\$ only on failure.

Expects a string and returns [k',p].

n=>(q=n.replace(n%3,''))%3?[q%11?q/10|0:q,11]:[q,3]

Try it online!

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

JavaScript (Node.js), 64 bytes, string input

f=(x,p=9n)=>BigInt(a=x.replace(p%3n,''))%(b=p/3n)?f(x,-~p):[a,b]

Try it online!

JavaScript (Node.js), 68 bytes

f=(x,k=1n,p=3n)=>(a=x%k+x/k/10n*k)>p>a%p?[a,p]:f(x,p>5?k*10n:k,8n^p)

Try it online!

Fast. Use fact that input is only 1 and 2.

Proof that it's always possible: For all 1 or 2, remove one digit if odd number of digits, then it's always 11x10101; Otherwise, one of keep, remove a 1, and remove a 2 result 0 modulo 3

Neil:Edge case 111 falls under 0 modulo 3 case.

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

Retina 0.8.2, 47 bytes

.|$
$`$'¶
.+
$*
1G`^(..+)\1+$
(..+)\1+$
$.& $.1

Try it online! Link includes faster test cases. Removes the earliest possible digit. Explanation:

.|$
$`$'¶

List the number with each digit removed in turn, then end with the original input.

.+
$*

Convert all of the numbers to unary.

1G`^(..+)\1+$

Keep only the first composite number.

(..+)\1+$
$.& $.1

Convert it and its highest proper factor to decimal.

In Retina 1 you would be able to fold those last two stages into a single stage, something like this:

0L$m`^(..+)\1+$
$.& $.1

(The m flag is not needed in Retina 0.8.2 because there the G stage type splits the input into lines and then matches each line in turn against the regex.)

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

Pyth, 12 bytes

eP
e-#PTsMy`

Try it online!

Explanation

                # implicitly assign Q = eval(input())
ePe-#PTsMy`Q    # implicitly add Q
          `Q    # str(Q)
         y      # powerset
       sM       # map to integers
   -#PT         # filter for non-primes
  e             # print last value in list
eP              # print largest prime factor of value
\$\endgroup\$
0
\$\begingroup\$

Vyxal 3 o, 18 bytes

Ṅ[ṢḶṪ⸠LĠt“⌊ᶻṄh]ỌḄt

Try it Online!

prints k' and the largest prime factor

Ṅ[ṢḶṪ⸠LĠt“⌊ᶻṄh]ỌḄt­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁤⁣‏⁠‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁤‏⁠⁠‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌­
Ṅ                   # ‎⁡is prime?
 [                  # ‎⁢
  ṢḶṪ               # ‎⁣group sublists by length and drop the tail 
     ⸠LĠt           # ‎⁤group by max length, take the longest
         “⌊ᶻṄ       # ‎⁢⁡convert to number and filter by not prime
             h      # ‎⁢⁢take the first number left
              ]     # ‎⁢⁣
               Ọ    # ‎⁢⁤print k'
                Ḅt  # ‎⁣⁡largest prime of k'
💎

Created with the help of Luminespire.

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 10 bytes

æʒp≠}θDÒθ‚

Try it online or verify all test cases.

Explanation:

æ        # Get the powerset of the (implicit) input
 ʒ       # Filter, only keeping those which are:
   ≠     #  NOT
  p      #  a prime number
 }θ      # After the filter: pop and keep the last/maximum
   D     # Duplicate it
    Ò    # Pop and get its prime factors
     θ   # Pop and keep the last/maximum again
      ‚  # Pair the two together
         # (after which this pair is output implicitly as result)

The ʒp≠} can be a number of other things with a similar result: ÐpÏK; DÒ˜K; ¤ÅPK.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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