17
\$\begingroup\$

Challenge:

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:

Input:

987654321

Output:

379721
10593529
1091
179
1493
293
19
7

Alternately:

[379721,10593529,1091,179,1493,293,19,7]

This prints the largest prime factors of 987654321, 876543219 = 4237411610, 76543218 = 205435310, and so on until it reaches 12, where it stops.

\$\endgroup\$
  • 2
    \$\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 '16 at 23:47
  • \$\begingroup\$ Welcome to the site! \$\endgroup\$ – DJMcMayhem Apr 11 '16 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 '16 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 '16 at 0:53
  • 3
    \$\begingroup\$ Any chance this was inspired by Google Code Jam? \$\endgroup\$ – Mego Apr 11 '16 at 1:16
6
\$\begingroup\$

Pyth, 25 bytes

sfTm>1PiFdC,.u-N`tYKrT1zK
                       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.

\$\endgroup\$
4
\$\begingroup\$

Pyth - 16 bytes

V_S9#ePi~-z`NhNB

Try it online here.

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

\$\endgroup\$
4
\$\begingroup\$

MATL, 17 15 bytes

9:PQ"G@ZAYfXzX>

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

Try it online!

Explanation

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
\$\endgroup\$
  • \$\begingroup\$ This one outputs a 0 at the end for inputs not ending in 1. \$\endgroup\$ – poi830 Apr 11 '16 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 '16 at 0:21
  • 1
    \$\begingroup\$ @poi830 Solved now \$\endgroup\$ – Luis Mendo Apr 11 '16 at 0:25
1
\$\begingroup\$

Julia, 101 bytes

f(s,x=[],b=10)=(t=filter(c->c<=47+b,s))>"1"&&b>1?f(s,[x;maximum(keys(factor(parse(Int,t,b))))],b-1):x

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

Ungolfed:

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)
    else
        # Otherwise return the array
        x
    end
end
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 83 bytes

FactorInteger[Select[IntegerDigits@#,#<a&]~FromDigits~a][[-1,1]]~Table~{a,10,2,-1}&

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

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

Ruby, 120 bytes

Recursive function, takes the input as a string.

f=->n,b=2{require'prime';i=n.tr([*b.to_s..?9].join,"").to_i(b)
b>10?[]:f[n,b+1]+[*i>1?Prime.prime_division(i).max[0]:p]}
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save some bytes by using the -rprime command line flag instead of require. \$\endgroup\$ – Doorknob Apr 11 '16 at 10:59
  • \$\begingroup\$ -rprime doesn't work for me for some reason... \$\endgroup\$ – Value Ink Apr 11 '16 at 17:23
0
\$\begingroup\$

Pyke, 19 bytes, noncompeting

(add splat_node functon)
DTAbPe
;1TtD=T`"":r

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