You are given a base 10 number. For each base from 10 counting down to base 2:

  1. Take the original input number as a base 10 string, and remove any digits of the number which are invalid for the base.
  2. Interpret the resulting number string in the that base. If this gives 1 or 0, terminate the whole process.
  3. Output or print its largest prime factor, as decimal number.

The output can be an array of the largest prime factors.

Sample cases:







This prints the largest prime factors of \$987654321\$, \$87654321_9 = 42374116_{10}\$, \$7654321_{8} = 2054353_{10}\$, and so on until it reaches \$1_2\$, where it stops.

  • 3
    \$\begingroup\$ I'm unclear on the process. I could probably figure it out from the example, but you should have clear instructions so this isn't needed. So we convert to a lower base, remove invalid digits, then print the largest prime factor? What base do we print this factor in? Do we then do the same process with the largest prime factor and a base one lower? Or do we do it with the number we factored? Do we start with 10 or 9? \$\endgroup\$
    – xnor
    Apr 10, 2016 at 23:47
  • \$\begingroup\$ Welcome to the site! \$\endgroup\$
    – DJMcMayhem
    Apr 11, 2016 at 0:08
  • 2
    \$\begingroup\$ I tried rewriting the challenge to make it clearer. I hope this is what you intended. If not, feel free to change it. \$\endgroup\$
    – xnor
    Apr 11, 2016 at 0:31
  • 4
    \$\begingroup\$ I find the largest-prime-factor step rather tacked on to the main operation is base conversion. Many languages just do it directly with a prime-factorization built-in, and the rest basically have to do a second separate challenge. Base conversion is also built-in-or-bust. When operations come as built-ins, you expect them to be well-trodden ground for golfs, and indeed factorization and base conversion are. Still, good for a first challenge, but things to keep in mind for next time. \$\endgroup\$
    – xnor
    Apr 11, 2016 at 0:53
  • 3
    \$\begingroup\$ Any chance this was inspired by Google Code Jam? \$\endgroup\$
    – user45941
    Apr 11, 2016 at 1:16

8 Answers 8


Pyth, 25 bytes

                       z   get input as a string
            .u      rT1    cumulative reduce over [10,9,...,2]
              -N`tY        remove one minus the number (10,9,...) from the input
          C,       K    K  pair each step along the chain with corresponding base
   m                       map over [["987654321", 10],...]:
       iFd                   apply the base-conversion (splat over i)
      P                      prime factorization, smallest to largest
    >1                       take [the last element], or [] if empty (1 or 0)
 fT                        remove the []s from 0s or 1s
s                          join the one-element arrays together

Try it here.


Pyth - 16 bytes


Try it online here.

There are sometimes a few blank lines on inputs without all the digits, lemme know if that's a problem.


MATL, 17 15 bytes


This takes the number as a string with quotes, which is allowed by default.

Try it online!


9:PQ     % Push array [10, 9, ..., 2]
"        % For each number in that array. These are the bases to be considered
  G      %   Push input. Forces for input to be taken implicitly first time
  @      %   Push current base
  ZA     %   Convert from that base to base 10, discarding non-valid digits
  Yf     %   Prime factors. Gives empty for input 1, and 0 for input 0
  Xz     %   Non-zero values. Gives empty if previous result was 0, or else
         %   leaves it as it was
  X>     %   Maximum of array. For empty input gives empty
         % Implicitly end for each
         % Implicitly display. Empty arrays are not displayed
  • \$\begingroup\$ This one outputs a 0 at the end for inputs not ending in 1. \$\endgroup\$
    – poi830
    Apr 11, 2016 at 0:18
  • \$\begingroup\$ For the inputs '98765432' and '98765' (random examples), it output the correct numbers then 0 before terminating. \$\endgroup\$
    – poi830
    Apr 11, 2016 at 0:21
  • 1
    \$\begingroup\$ @poi830 Solved now \$\endgroup\$
    – Luis Mendo
    Apr 11, 2016 at 0:25

Julia, 101 bytes


This is a recursive function that accepts the input as a string and returns an array.


function f(s, x=[], b=10)
    # Filter the string down to only the digits valid for base b
    t = filter(c -> c <= 47 + b, s)

    # If the filtered string isn't "1" or "0" and b is a valid base
    if t > "1" && b > 1
        # Call the function again, appending the maximum prime factor
        # of t in base b to the argument x and decrementing the base
        f(s, [x; maximum(keys(factor(parse(Int, t, b))))], b-1)
        # Otherwise return the array

Mathematica, 83 bytes


Anonymous function, returns a list. Not that complicated, to be honest.


Jelly, 14 bytes


Try it online!

How it works

D<ƇḅṛɗⱮ⁵ÆfṀ€t0 - Main link. Takes an integer n on the left
D              - Cast n to digits, D
     ɗ         - Previous 3 links as a dyad f(D, k):
 <Ƈ            -   Keep elements of D less than k
    ṛ          -   Yield k
   ḅ           -   Convert to base k
       ⁵       - 10
      Ɱ        - Yield the range 1 ≤ k ≤ 10 and map f(D, k) over each
        Æf     - Prime factors
          Ṁ€   - Maximum of each, or 0 if empty list
            t0 - Trim zeros

Ruby, 120 bytes

Recursive function, takes the input as a string.

  • 1
    \$\begingroup\$ You can save some bytes by using the -rprime command line flag instead of require. \$\endgroup\$
    – Doorknob
    Apr 11, 2016 at 10:59
  • \$\begingroup\$ -rprime doesn't work for me for some reason... \$\endgroup\$
    – Value Ink
    Apr 11, 2016 at 17:23

Pyke, 19 bytes, noncompeting

(add splat_node functon)

Try it here!

Takes input in quotes, exits with an error.

Explanation (newline replaced with \n):

D                    - Duplicate the first item on the stack (And get it from input first time)
 TAb                 - Convert input to base (whatever's in T, 10 default)
    Pe               - get the highest prime factor of the number
      \n;1           - print it out and get rid of it
          TtD=T      - T -= 1
               `"":  - input = input.replace(str(t), "")
                   r - GOTO start

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.