15
\$\begingroup\$

Based on a chat message

The Challenge

Given an input number n > 9, construct its reverse, ignoring leading zeros. Then, construct a list of all prime factors that the number and its reverse don't have in common. Multiply those factors together to create the Uncommon Factor Number of the input.

Or, to put it another way: if rev(n) denotes the decimal reversal of integer n, calculate the product of n and rev(n) divided by the square of the gcd(n, rev(n)).

Output that number.

Worked examples

For example, 2244 reverses to 4422. The prime factors of the first are [2, 2, 3, 11, 17] and the prime factors of the reverse are [2, 3, 11, 67]. The numbers not in common multiplicities are [2, 17, 67], so 2278 is the output.

For another example, 1234 reverses to 4321. The product is 5332114 and the GCD is 1, so the output is 5332114.

Further clarifications

Obviously a palindromic number will have all its factors in common with its reverse, so in such a case the output is 1 (n*n/n^2). Obviously, it's also possible for the output to be the multiplication all factors (i.e., the gcd is 1 -- the input and its reverse are co-prime), as in the case of the 1234 example.

Rules

  • The input and output can be assumed to fit in your language's native integer type.
  • The input and output can be given in any convenient format.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

in
out

17
1207

208
41704

315
1995

23876
101222302
\$\endgroup\$
  • \$\begingroup\$ Can we assume the input will not have leading zeros? \$\endgroup\$ – Mr. Xcoder Sep 8 '17 at 14:48
  • 1
    \$\begingroup\$ @Mr.Xcoder Huh? You mean trailing zeroes? \$\endgroup\$ – Erik the Outgolfer Sep 8 '17 at 14:50
  • \$\begingroup\$ @EriktheOutgolfer No, leading zeros is exactly what I mean. Also \$\endgroup\$ – Mr. Xcoder Sep 8 '17 at 14:50
  • 3
    \$\begingroup\$ The second test case should be 1995 (I believe) \$\endgroup\$ – Mr. Xcoder Sep 8 '17 at 14:53
  • 1
    \$\begingroup\$ @LuisMendo Thanks. Good addition. \$\endgroup\$ – AdmBorkBork Sep 8 '17 at 15:14

19 Answers 19

6
\$\begingroup\$

05AB1E, 6 bytes

Code

‚D¿÷P

Uses the 05AB1E encoding. Try it online!

Explanation

‚        # Get the array [input, reversed(input)]
  D       # Duplicate that array
   ¿      # Calculate the GCD of the array
    ÷     # Divide each element in the array by the GCD
     P    # Product of that array
\$\endgroup\$
  • \$\begingroup\$ A nice, simple alternative to the formula provided in the challenge - +1. Tried the same in Japt but it came out 2 bytes longer than what I already had. \$\endgroup\$ – Shaggy Sep 8 '17 at 23:42
5
\$\begingroup\$

J, 18 bytes

".@|.@":(*%*:@+.)]

Try it online!

Alternatively (credit to @Adnan's approach for the second one),

".@|.@":(*%2^~+.)]
".@|.@":*/@(,%+.)]

J, 15 bytes (@miles's solution)

*/@(,%+.)|.&.":

Explanation

This is just a straightforward implementation of the algorithm given by the OP.

".@|.@":(*%*:@+.)]
                 ]  n (input)
".@|.@":            n reversed
         *          Product of the two
          %         Divided by
              +.      GCD
           *:         Squared

Explanation, @miles's solution

Very clever.

*/@(,%+.)|.&.":
         |.&.":  Reverse digits
           &.":   Convert to string, apply next function, and undo conversion
         |.       Reverse
   (,%+.)        Divide n and reverse(n) by GCD of both
*/               Product
\$\endgroup\$
  • 2
    \$\begingroup\$ 15 bytes with */@(,%+.)|.&.": \$\endgroup\$ – miles Sep 8 '17 at 16:57
  • \$\begingroup\$ @miles I love the under trick \$\endgroup\$ – cole Sep 8 '17 at 17:01
  • \$\begingroup\$ @miles that one is really slick. \$\endgroup\$ – Jonah Sep 8 '17 at 18:54
  • \$\begingroup\$ Why not submit the 15 byte version as your main solution? \$\endgroup\$ – Shaggy Sep 8 '17 at 23:39
  • \$\begingroup\$ @Shaggy Not sure. My inclination was to respond with "it's significantly different from my own," but it's really just two optimizations. I'll get to updating it later. \$\endgroup\$ – cole Sep 9 '17 at 0:50
4
\$\begingroup\$

Mathematica, 33 bytes

#(s=IntegerReverse@#)/GCD[#,s]^2&

Try it online!

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

Jelly, 8 bytes

,ṚḌµ:g/P

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Dammit, I had exactly the same (except DU instead of ) \$\endgroup\$ – ETHproductions Sep 8 '17 at 14:54
  • \$\begingroup\$ @ETHproductions Yeah on an integer reverses the digits but doesn't convert back to an integer. \$\endgroup\$ – Erik the Outgolfer Sep 8 '17 at 15:07
2
\$\begingroup\$

JavaScript (ES7), 67 64 bytes

So many bytes just to reverse the number :(

Takes input as a string.

n=>n*(x=[...n].reverse().join``)/(g=(y,z)=>z?g(z,y%z):y)(n,x)**2

Try it

o.innerText=(f=
n=>n*(x=[...n].reverse().join``)/(g=(y,z)=>z?g(z,y%z):y)(n,x)**2
)(i.value="10");oninput=_=>o.innerText=f(i.value)
<input id=i min=10 type=number><pre id=o>

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

Haskell, 44 bytes

f x|r<-read$reverse$show x=x*r`div`gcd x r^2

Try it online!

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

R, 108 89 bytes

-19 bytes thanks to plannapus for his gcd algorithm

function(n){k=1:nchar(n)-1
q=1:n
(r=sum(n%/%10^k%%10*10^rev(k)))*n/max(q[!r%%q&!n%%q])^2}

This will attempt to allocate at least one vector of size 4*n bytes (and I think as many as 4), so this will throw a memory error for sufficiently large n.

Try it online!

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

Python 3, 73 68 bytes

-5 bytes thanks to Mr. Xcoder.

import math
def f(n):g=int(str(n)[::-1]);print(n*g/math.gcd(n,g)**2)

Try it online!

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

MATL, 13 12 11 bytes

tVPU*1MZdU/

Try it online! Or verify all test cases.

Explanation

t      % Imoplicit input: number. Duplicate
VPU    % String representation, flip, evaluate. This reverses digits
*      % Multiply input and reversed-digit version
1M     % Push the input and reversed-digit version again
Zd     % Greatest common divisor
U      % Square
/      % Divide. Implicit display
\$\endgroup\$
1
\$\begingroup\$

Neim, 11 bytes

𝕓𝕋₁𝐫𝐕₁𝐕𝕌𝐠ᛦ𝕍

Try it online!

No GCD built-in. ;-;

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

Husk, 10 bytes

S¤§÷o□⌋*i↔

Try it online!

-1 thanks to H.PWiz.
-1 thanks to Zgarb.

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

Japt, 13 12 11 bytes


sw
*V/yU ²

Try it


Explanation

Implicit input of integer U. The empty line at the beginning, prevents the following line from overwriting U

sw

Convert U to a string (s), reverse it (w), convert back to an integer and assign to variable V.

*V

Multiply U by V.

/

Divide.

yU

GCD of V and U.

²

Squared. Implicit output of resulting integer.


Alternative, 13 bytes

Just because I like being able to use N.

NpUsw)mxNry)×

Try it

\$\endgroup\$
  • \$\begingroup\$ Smart trick with GCD. I think that algorithm might actually be shorter than the current Jelly solution... \$\endgroup\$ – ETHproductions Sep 8 '17 at 15:03
  • \$\begingroup\$ @ETHproductions In Jelly GCD ends up being longer... \$\endgroup\$ – Erik the Outgolfer Sep 8 '17 at 15:08
  • \$\begingroup\$ @EriktheOutgolfer I "have" an 8-byte version, but this involves dividing the results of two dyads and I'm not sure how to properly do that... \$\endgroup\$ – ETHproductions Sep 8 '17 at 15:34
1
\$\begingroup\$

Pyth, 13 bytes

/*QKs_`Q^iKQ2

Try it here!

Pyth, 15 bytes

This uses Adnan's approach and takes input as a String.

KsM_BQ*Fm/diFKK

Try it here

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

x86 Machine Code, 39 bytes

;;; Obtain a "reversed" version of the input value.
;;; 
;;; To do this, each iteration of a loop, we take the input value modulo 10,
;;; add that to our accumulator (EDI), multiply the accumulator by 10, and
;;; divide the input value by 10. x86's DIV instruction does both modulo and
;;; division as a single operation, with the cost of clobbering two output
;;; registers (EAX and EDX). We clobber the input value throughout the loop
;;; (the way we know we're done is when it becomes 0---that means that we have
;;; pulled all of the digits off of it), so we need to save a copy of it first.
89 C8           mov    eax, ecx     ; make copy of input
31 FF           xor    edi, edi     ; clear accumulator
6A 0A           push   10
5E              pop    esi          ; set ESI to 10
             Reverse:
0F AF FE        imul   edi, esi     ; accumulator *= 10
99              cdq                 ; zero EDX in preparation for division
F7 F6           div    esi          ; EDX:EAX / 10 (EAX is quot, EDX is rem)
01 D7           add    edi, edx     ; accumulator += remainder
85 C0           test   eax, eax     ; was quotient 0?
75 F4           jnz    Reverse      ; if not, keep looping and extracting digits

;;; At this point, EAX is 0 (clobbered throughout the loop),
;;; ECX still contains a copy of our original input, and
;;; EDI contains the 'reversed' input.
89 C8           mov    eax, ecx     ; make another copy of the input
F7 E7           mul    edi          ; multiply input (implicit EAX operand)
                                    ;  by 'reversed', with result in EDX:EAX
                                    ;  (note: EDX will be 0)

;;; Compute the greatest common denominator (GCD) of the input and
;;; the 'reversed' values, using a subtraction-based algorithm.
             GCD_0:
39 CF           cmp    edi, ecx     ; compare the two values
72 02           jb     GCD_1        ; go to GCD_1 if less than
87 F9           xchg   ecx, edi     ; swap values
             GCD_1:
29 F9           sub    ecx, edi     ; subtract
75 F6           jnz    GCD_0        ; if sum != 0, go back to the top

;;; Square the GCD.
0F AF FF        imul   edi, edi

;;; Divide the product of input and 'reversed' by the square of the GCD.
;;; Remember from above that the product of input and 'reversed' is in
;;; the EAX register, and we can assume EDX is 0, so we don't need to do
;;; a CDQ here in preparation for the division. Using EAX as the implicit
;;; source operand saves us a byte when encoding DIV.
F7 F7           div    edi

;;; The DIV instruction placed the quotient in EAX,
;;; which is what we want to return to the caller.
C3              ret

The above function computes the "uncommon factor number" of the specified input parameter. Following the register-based __fastcall calling convention, the parameter is passed in the ECX register. The result is returned in the EAX register, as with all x86 calling conventions.

Try it online!

This took an awfully long time to write in such a compact form, but it was a fun exercise. Lots of contortions to get the most optimal register scheduling possible, within the constraints of the x86 DIV instruction's implicit operands and trying to use short encodings of MUL and XCHG instructions whenever possible. I'd be very curious to see if someone can think of another way to shorten it further. My brain was quite fried by the end. Thank a compiler next time you see one! (Although this is way better code than what a compiler would generate... Especially if you tweaked it slightly without size constraints, removing things like XCHG.)

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

Perl 5, 72 bytes

71 bytes of code + 1 flag (-p)

$t=$_*($b=reverse);($_,$b)=(abs$_-$b,$_>$b?$b:$_)while$_-$b;$_=$t/$_**2

Try it online!

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

Pyke, 8 bytes

_]FbP).^B

Try it here!

Takes input as a string.

_         -    reversed(input)
 ]        -   [^, input]
  FbP)    -  for i in ^:
   b      -     int(^)
    P     -    factors(^)
      .^  -  xor_seq(^)
        B - product(^)
\$\endgroup\$
0
\$\begingroup\$

Python 2, 70 bytes

Thanks to i cri everytim.

def f(n):g=int(`n`[::-1]);print n*g/gcd(n,g)**2
from fractions import*

Try it online!

Python 2, 77 bytes

Note that in Python 2, you cannot use the math.gcd() method, and you must do it "by hand".

y=lambda a,b:b and y(b,a%b)or a
def f(n):g=int(`n`[::-1]);print n*g/y(n,g)**2

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Python 3 has gcd as fractions.gcd. \$\endgroup\$ – totallyhuman Sep 8 '17 at 17:52
  • \$\begingroup\$ @icrieverytim That's why I chose to solve it in Python 2. \$\endgroup\$ – Mr. Xcoder Sep 8 '17 at 18:00
  • \$\begingroup\$ ...Whoops, I meant Python 2. Python 3 has math.gcd. \$\endgroup\$ – totallyhuman Sep 8 '17 at 18:15
  • \$\begingroup\$ @icrieverytim done. \$\endgroup\$ – Mr. Xcoder Sep 8 '17 at 18:17
0
\$\begingroup\$

Ohm, 9 bytes

DR«D]Æ┴/µ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ psst... Ohm v2 is out and better than ever! \$\endgroup\$ – Nick Clifford Sep 10 '17 at 0:35
0
\$\begingroup\$

Java 8, 158 150 148 138 125 123 116 107 + 19 bytes

i->{int o,r,f,t=f=i;i=r=i.valueOf(""+new StringBuffer(t+"").reverse());while(t>0)t=i%(i=t);return f/i*r/i;}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ In the while loop, you can replace t!=0 by t>0, since t will never be negative. f*r/(i*i) is the same as f/i*r/i. You can drop f=t; and r=i; if you chain the assignment of i and t. \$\endgroup\$ – Luke Sep 9 '17 at 7:57
  • 1
    \$\begingroup\$ The while loop can be written as while(t>0)t=i%(i=t); (-11 bytes). \$\endgroup\$ – Nevay Sep 11 '17 at 11:24

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.