Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Your task is to turn a square root like this:
√12
into a form like this:
2√3
For our purpose, we only need to output the left number here:
2
4 -> 2
9 -> 3
12 -> 2
13 -> 1
108-> 6
√4 = 2√1 -> 2
√13 = 1√13 -> 1
-mx, Crossed out  4; is no longer 4 :)
²vN
My first Japt answer. :)
Port of my first 5-byter 05AB1E answer, but with smart use of Japt's flags for the range and sum.
-1 byte thanks to @Shaggy thanks to the shortcuts list: p)/p␠ to ²
Explanation:
-m # Convert the (implicit) input-integer to a ranged list [0, input)
² # Square each value in the list, and implicitly close the function
vN # Check which values are divisible by the input (1 if truthy; 0 if falsey)
-x # After which the sum is calculated of the resulting list
# (before the result is output implicitly)
-mx) since Dec. 2017.
\$\endgroup\$
– Kevin Cruijssen
Jul 8 '20 at 15:05
1. a space is enough to close a single method in Japt (although the ) doesn't make a difference here 2. There's a shortcut for ` p2<space>` which will allow you to get this down to 3 bytes.
\$\endgroup\$
– Shaggy
Jul 8 '20 at 15:10
õ²xvU would do it for 5 bytes, Kevin.
\$\endgroup\$
– Shaggy
Jul 8 '20 at 16:00
LnIÖO
Try it online or verify all test cases.
Previous 9 6 bytes approach:
LR.ΔnÖ
-3 bytes thanks to @ovs.
Try it online or verify all test cases.
Explanation:
L # Push a list in the range [1, (implicit) input]
n # Take the square of each value in the list
IÖ # Check which squares are divisible by the input (1 if truthy; 0 if falsey)
O # And sum those checks
# (after which this sum is output implicitly as result)
L # Push a list in the range [1, (implicit) input]
R # Reverse it to [input, 1]
.Δ # Find the first value in this list which is truthy for:
n # Square the current value
Ö # Check if the (implicit) input is evenly divisible by this square
# (after which the found value is output implicitly as result)
Ó; the best I could do was Ó2÷ā<ØsmP, which is as long as your first answer, but hopefully more efficient at least.
\$\endgroup\$
– Neil
Jul 9 '20 at 0:10
Ó2÷ā<ØsmP. I like this challenge, because there are quite a few slightly different approaches to get the same answers. :) And it's indeed unfortunate there isn't an inverse of Ó in this case.
\$\endgroup\$
– Kevin Cruijssen
Jul 9 '20 at 7:12
Ḷ²%ċ0
Uses the formula from the OEIS: the number of solutions to $$x^2 \equiv 0 \ (\mathrm{mod} \ n)$$ Explanation:
0..n-1,
ḍ²€S TIO. That is, square each of the implicit [1..n] with ²€, check if n divides each with ḍ (same result for n² as you'd get for 0²), then sum with S.
\$\endgroup\$
– Jonathan Allan
Sep 11 '20 at 12:26
ÆE:2ÆẸ
A monadic Link accepting a positive integer which yields a positive integer.
Try it online! Or see the first 100.
ÆE:2ÆẸ - Link: integer, X e.g. 9587193
ÆE - factorisation vector (X) [0,1,0,4,3] (since 2°×3¹×5°×7⁴×11³=9587193)
:2 - integer divide by two [0,0,0,2,1]
ÆẸ - evaluate factorisation vector 539 (since 2°×3°×5°×7²×11¹=539)
(this was produced by trying a bunch of languages from https://github.com/ETHproductions/golfing-langs until I found one that had the most useful built-ins for this problem)
dụ⁇)u
Explanation:
d divisors
ụ⁇ keep only squares
) take last
u square root
As per the exception described in this meta answer, the exact score is 21.25 bytes (170 bits)
A routine expecting the input number in R0 and returning the result in R3.
1D2 | CLRR R2
1C9 | CLRR R1
0D1 | @@loop ADDR R2, R1
00A | INCR R2
084 | MOVR R0, R4
10C | @@sub SUBR R1, R4
10C | SUBR R1, R4
114 | SUBR R2, R4
22E 004 | BGT @@sub
20C 001 | BNEQ @@next
093 | MOVR R2, R3
141 | @@next CMPR R0, R1
226 00D | BLE @@loop
0AF | JR R5
The CP-1610 has no multiplication, no division, no modulo. We want to implement an algorithm that relies on additions and subtractions exclusively.
We start with \$k=0\$. At each iteration, we update \$j\$ in such a way that:
$$j = \frac{k(k-1)}{2}$$
The good thing about this formula is that it's very easy to compute iteratively: we just need to add \$k\$ to \$j\$ and increment \$k\$ afterwards.
In order to test whether \$n\$ is divisible by \$k^2\$, we initialize a variable \$x\$ to \$n\$ and subtract \$k^2\$ until \$x\le 0\$.
We do not explicitly store \$k^2\$, but it can be easily obtained with:
$$2j+k=k(k-1)+k=k^2$$
Each time we end up with \$x=0\$, we update the final answer to \$k\$.
We stop when \$j\$ is greater than \$n\$.
Here is a link to an implementation of the algorithm in low-level JS.
ROMW 10 ; use 10-bit ROM width
ORG $4800 ; map this program at $4800
PNUM QEQU $18C5 ; EXEC routine: print a number
MULT QEQU $1DDC ; EXEC routine: signed multiplication
;; ------------------------------------------------------------- ;;
;; main code ;;
;; ------------------------------------------------------------- ;;
main PROC
SDBD ; set up an interrupt service routine
MVII #isr, R0 ; to do some minimal STIC initialization
MVO R0, $100
SWAP R0
MVO R0, $101
EIS ; enable interrupts
MVII #$200, R3 ; R3 = backtab pointer
SDBD ; R4 = pointer to test cases
MVII #@@tc, R4
@@loop MVI@ R4, R0 ; R0 = next test case
TSTR R0 ; stop if it's 0
BEQ @@done
PSHR R4 ; save R4
PSHR R3 ; save R3
CALL pSquare ; invoke our routine
MOVR R3, R0 ; copy the result into R0
PULR R3 ; restore R3
CALL print ; print the result
PULR R4 ; restore R4
B @@loop ; go on with the next test case
@@done DECR R7 ; done: loop forever
;; test cases
@@tc DECLE 4, 9, 12, 13, 108, 300, 800, 900
DECLE 0
ENDP
;; ------------------------------------------------------------- ;;
;; prints the result of a test case ;;
;; ------------------------------------------------------------- ;;
print PROC
PSHR R5 ; save the return address on the stack
MVII #4, R1 ; R1 = number of digits
MOVR R3, R4 ; R4 = backtab pointer
ADDI #5, R3 ; advance by 5 characters for the next one
PSHR R3 ; save R3
CLRR R3 ; R3 = attributes (black)
CALL PNUM ; invoke the EXEC routine
PULR R3 ; restore R3
PULR R7 ; return
ENDP
;; ------------------------------------------------------------- ;;
;; ISR ;;
;; ------------------------------------------------------------- ;;
isr PROC
MVO R0, $0020 ; enable display
MVI $0021, R0 ; color-stack mode
CLRR R0
MVO R0, $0030 ; no horizontal delay
MVO R0, $0031 ; no vertical delay
MVO R0, $0032 ; no border extension
MVII #$D, R0
MVO R0, $0028 ; light-blue background
MVO R0, $002C ; light-blue border
MVO R0, $002C ; light-blue border
JR R5 ; return from ISR
ENDP
;; ------------------------------------------------------------- ;;
;; our routine ;;
;; ------------------------------------------------------------- ;;
pSquare PROC
CLRR R2 ; R2 = k
CLRR R1 ; R1 = k(k - 1) / 2
@@loop ADDR R2, R1 ; add R2 to R1
INCR R2 ; k++
MOVR R0, R4 ; start with R4 = n
@@sub SUBR R1, R4 ; subtract 2 * (k(k - 1) / 2) = k² - k
SUBR R1, R4 ; from R4
SUBR R2, R4 ; subtract k from R4
BGT @@sub ; until R4 is less than or equal to 0
BNEQ @@next ; did we reach exactly 0? ...
MOVR R2, R3 ; ... yes: update R3
@@next CMPR R0, R1 ; go on while R1 is less than or
BLE @@loop ; equal to R0
JR R5 ; return
ENDP
This is the output for the following test cases:
4, 9, 12, 13, 108, 300, 800, 900
screenshot from jzIntv
1. A CP-1610 opcode is encoded with a 10-bit value (0x000 to 0x3FF), known as a 'DECLE'.
.+
$*
((^1|11\2)+)\1*$
$#2
Try it online! Link includes test cases. Explanation:
.+
$*
Convert to unary.
((^1|11\2)+)
Find the largest square number...
\1*$
... that divides the input...
$#2
... and output its root.
Bonus 63-byte version that for an input of √1, √2, √3, √4, √5, √6, √7, √8, √9... outputs 1, √2, √3, 2, √5, √6, √7, 2√2, 3... etc. (Previous bonus version did not handle √1 correctly.)
\d+
$*
r`(?=^.(\3)+)(.)\3*((1$|11\4)+)
$#4$2$#1
\D1$
^1(\D)
$1
f n=sum[0^mod(x^2)n|x<-[1..n]]
Based on the solution of my pronoun is monicareinstate, counting the number of solutions to \$x^2 \equiv 0 \ (\mathbb{mod}\ n)\$ using the range from 1 to n.
f n=until((<1).mod n.(^2))pred n
Start with n and repeatedly take the predecessor, until it satiafies this condition: when we square it and take the original n modulo it, the result is less than 1, that is equal to 0.
√#/._^_:>1&
For an integer argument, √ (Sqrt) returns in the desired a√b form (unless the argument was a perfect square).
Then, /._^_:>1 matches Power expressions and replaces them with 1. As a√b expands to Times[a,Power[b,1/2]], it becomes Times[a,1]=a.
-1 thanks to Unrelated String
f↔∋√ℕ
f↔∋√ℕ
ℕ output is a natural number (≥0) that is
√ the root of … (Brachylog gives the negative root first)
∋ an element …
f↔ in the reverse factors list (so search starts with bigger values)
{ḋp⊇~j×}ᵘ⌉
Try it online! or verify all test cases.
{ḋp⊇~j×}ᵘ⌉
⌉ take the maximum of …
{ }ᵘ all unique …
× multiplications of … 10
~j halves of … [2,5]
⊇ ordered subsets from … [2,5,2,5]
p the permutations of … [2,5,2,5,3]
ḋ the prime factors [2,2,3,5,5]
~^₂ for the same byte count...
\$\endgroup\$
– Unrelated String
Sep 11 '20 at 12:08
n->core(n,1)[2]
Yes, there is a build-in.
core(n,{flag=0}): unique squarefree integerddividingnsuch thatn/dis a square. If (optional) flag is non-null, output the two-component row vector[d,f], wheredis the unique squarefree integer dividingnsuch thatn/d=f^2is a square.
n->{for(var c=n++;c/--n%n>0;);return n;}
Inspired by @Arnauld's JavaScript answer, so make sure to upvote him!
Explanation:
n->{ // Method with double as both parameter and return-type
for(var c=n // Create a copy `c` of the input `n`
++ // Then increase `n` by 1
; // Continue looping as long as:
c/--n // (decrease `n` by 1 first before every iteration with `--n`)
// `c` divided by `n`
%n>0;) // is NOT a multiply of `n` nor 0
;return n;} // After the loop: return the modified `n` as result
f=(n,k=n)=>n/k%k?f(n,k-1):k
We recursively look for the greatest \$k\le n\$ such that \$\dfrac{n}{k}\equiv 0\pmod k\$, which is guaranteed to be satisfied for \$k=1\$ in the worst case.
This is a more golf-friendly way of testing \$\dfrac{n}{k^2}\equiv 0\pmod 1\$.
((n=scan()):1)[!n%%(n:1)^2][1]
Or, a completely-different 25 byte approach based on equivalence to 'number of solutions to x^2==0(mod n)' (as pointed-out by my pronoun is monicareinstate), but that wasn't my own idea and hence seems to me to be cheating:
sum(!(1:(n=scan()))^2%%n)
n=i=input()
while n%i**2:i-=1
print i
38 bytes
lambda n:sum(x*x%n<1for x in range(n))
Based on the solution of my pronoun is monicareinstate, counting the number of solutions to \$x^2 \equiv 0 \ (\mathbb{mod}\ n)\$ for \$x\$ from \$0\$ to \$n-1\$.
q~_{_*1$%!},,\;
Uses the new method in Kevin Cruijssen's 05AB1E answer.
q~mF{[~2/]}%{~#}%{*}*
q~ Translate input into a CJam object (allows for easier testing)
mF Factorise with exponents
{ }% For each factor
~2/ Halve the exponent [and round down]
[ ] Capture the base & exponent in an array
{ }% For each transformed factor
~# Expand the base and exponent into b^e
{*}* Multiply all the transformed factors together
This approach removes all single factors (those that would make up the radical part) whilst halving the paired factors (equivalent to square rooting the integer part).
q~_,(;{_*1$\%0>!},\;)\;
Now based on @someone's formula.
ＮθＩＬΦθ¬﹪×ιιθ
Try it online! Link is to verbose version of code. For each number from 0 to the input, calculates whether its square is divisible by the input, and takes the number of matches.
Alternative version, also 12 bytes:
ＮθＩΣＥθ¬﹪×ιιθ
Try it online! Link is to verbose version of code. For each number from 0 to the input, calculates whether its square is divisible by the input, and takes the sum of the results.
Alternative version, also 12 bytes:
ＮθＩ№Ｅθ﹪×ιιθ⁰
Try it online! Link is to verbose version of code. For each number from 0 to the input, calculates the remainder when its square is divisible by the input, and counts the number of zeros.
ef!%Q^T2S
ef!%Q^T2S
S Create range from 1 to (implicit) input
f Filter keep from the above, as T, where:
^T2 Square T
%Q Mod the input with the above
! Logical NOT
e Take the last (largest) element of the filtered list, implicit print
▲f₁m√Ḋ
¬%1
Try it online! or Verify all test cases.
▲ # the maximum of ...
f₁ # ... filter on line 1 ...
m√ # ... map square root on ...
Ḋ # ... the list of divisors
¬ # The negation ...
%1 # ... of modulo with 1
# (x%1 == 0 iff x is a whole number)
$n=$_;$_=max grep!($n%$_**2),1..$n
This finds the largest square which properly divides the input number. Very inefficient as it tries all numbers from 1 up to the input.
·£æ9Š3nòy├
Unpacked: +v{!(v^2%}\~
Uses the formula from the OEIS page: the number of solutions to \$x^2≡0 (\mod n)\$
~ 1-range (inclusive) to
_ variable initialized to STDIN; implied
+\ folded with addition after
v{ mapping with block (key of v)
! Boolean NOT
( Begin expression
v
^ exponentiated by
2 two
% mod
_ implied
) End expression; implied
} End block
[S S S N
_Push_0][S N
S _Duplicate_0][T N
T T _STDIN_as_integer][T T T _Retrieve_input][S N
S _n=Duplicate_input][N
S S N
_Create_Label_LOOP][S T S S T N
_Copy_0-based_1st_input][S T S S T N
_Copy_0-based_1st_n][S N
S _Duplicate_n][T S S N
_Multiply][T S T T _Modulo][N
T S S N
_If_0_Jump_to_Label_PRINT_RESULT][S S S T N
_Push_1][T S S T _Subtract][N
S N
N
_Jump_to_Label_LOOP][N
S S S N
_Create_Label_PRINT_RESULT][T N
S T _Print_as_integer]
Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.
Try it online (with raw spaces, tabs and new-lines only).
Port of @Sok's Pyth answer, so make sure to upvote him! Whitespace doesn't have decimals, so his/her approach is ideal for Whitespace since it doesn't use square-root nor regular division, but only integers.
Explanation in pseudo-code:
Integer n = STDIN as integer
Integer r = n
Start LOOP:
Integer s = r * r
If(n % s == 0):
Jump to Label PRINT
r = r - 1
Go to next iteration of LOOP
Label PRINT:
Print r as integer to STDOUT
(implicitly stop the program with an error: no exit defined)
╒²k÷Σ
Port of my 5-byter 05AB1E answer.
Explanation:
╒ # Push a list in the range [1, (implicit) input]
# (could alternatively be `r` for a range [0, input) )
² # Square each value in this list
k÷ # Check which values are evenly divisible by the input (1 if truthy; 0 if falsey)
Σ # And sum those checks
# (after which the entire stack joined together is output implicitly as result)
{√⍵÷×/(∪a)/⍨2∣≢¨⊂⍨a←π⍵}
test:
f←{√⍵÷×/(∪a)/⍨2∣≢¨⊂⍨a←π⍵}
f 4
2
f 9
3
f 12
2
f 13
1
f 108
6
f 2×2×2×2×2×3×3
12
comment:
{√⍵÷×/(∪a)/⍨2∣≢¨⊂⍨a←π⍵}
π⍵ factor argument
a← save that in a list "a" of prime factors
⊂⍨ partition "a" in a list of list each element is ugual factors found
2∣≢¨ to each element of list of list find if number of elements is odd
×/(∪a)/⍨ so choice in ∪a the elements appear in list of list as odd and multiple them
⍵÷ divide the argument for the number of factor contained odd times
√ make sqrt of that
.+ We convert the input into unary
$&*_ $&*_ and create a copy for factor checking
{` (_+) START LOOP: We square the input by multiplying
$& $.1*$1 its string representation by its length
(?=^.* (_+) (_+))\2+ .+ We check if the square is a factor of the input
$.1 if so we replace the whole text with the current counter
(_*)_.* Otherwise we decrement the counter by one
$1 ---
-- IMPLICIT LOOP END --
-- IMPLICIT OUTPUT --
This approach is essentially a port of Kevin Cruijssen's 05AB1E answer.
It checks all the numbers from the input downwards until it finds a number whose square divides the original.
I've also switched from separating with newlines to separating with spaces because . is anti-newline.
* defaults to $&*_. This means that you don't need the $& at the start or the _ at the end.
\$\endgroup\$
– Neil
Jul 10 '20 at 21:32
{`_+$ instead (use $& instead of $1 on line 4)
\$\endgroup\$
– Neil
Jul 10 '20 at 21:33
i*i i n instead of n i i*i.
\$\endgroup\$
– Neil
Jul 10 '20 at 21:34
_ _+$ and a blank line 8 works. (Note that is is pre-reversal so it would be ^_+ _ if you reversed the order as suggested by my previous comment.)
\$\endgroup\$
– Neil
Jul 10 '20 at 21:36
a√b. \$\endgroup\$ – xnor Jul 8 '20 at 10:28n=0is an exceptional edge case that would be better to disallow, since 0 can be expressed as0√bora√0for anyaorb. And if we consider simplest form to mean takingaas big as possible ina√b, there's no limit on how bigacan be. \$\endgroup\$ – xnor Jul 8 '20 at 10:37aif there is more-than-onea√bsolution (as implied by xnor), or whether anyais Ok. If the former, I'll need to add one more byte to my answer. Suggest test case 108 to clarify (√108 = 2√27, and 3√12, as well as 6√3). \$\endgroup\$ – Dominic van Essen Jul 8 '20 at 12:00108is a nice additional test case. If either the lowest or highest (or any) \$a\$ would be allowed, an output of1would suffice for every possible input, since \$1\sqrt{b}\$ would be valid - in which case I could have a 0-byte solution in Retina. ;) \$\endgroup\$ – Kevin Cruijssen Jul 8 '20 at 12:29