35
\$\begingroup\$

Background

Euler's totient function φ(n) is defined as the number of whole numbers less than or equal to n that are relatively prime to n, that is, the number of possible values of x in 0 < x <= n for which gcd(n, x) == 1. We've had a few totient-related challenges before, but never one which is just calculating it.

The mapping of the totient function onto the whole numbers is OEIS A000010.

Challenge

Given an integer n > 0, calculate φ(n). You may take input through command-line arguments, standard input, function arguments, or anything else reasonable. You may give output through standard output, return values, or anything else reasonable. Anonymous functions are acceptable. You may assume that the input will not overflow your natural method of storing integers, e.g. int in C, but you must support inputs up to 255. If your language has a built-in totient function, you may not use it.

Examples

φ(1) => 1
φ(2) => 1
φ(3) => 2
φ(8) => 4
φ(9) => 6
φ(26) => 12
φ(44) => 20
φ(105) => 48

Shortest answer in bytes wins. If your language uses an encoding other than UTF-8, mention it in your answer.

\$\endgroup\$
4
  • 4
    \$\begingroup\$ Well there was this the other day. I don't think the repeated application makes a sufficient difference, but if anything I'd close the other one, because I also don't think the repeated application adds anything. That said, the bigger difference is that that one allowed built-ins and this one doesn't. \$\endgroup\$ Jun 22, 2016 at 7:14
  • \$\begingroup\$ Disallowing built-ins apparently has no impact on the answers. \$\endgroup\$ Jun 22, 2016 at 7:39
  • 2
    \$\begingroup\$ @JuliePelletier Why is that? My Mathematica answer would otherwise have been 19 bytes shorter: EulerPhi \$\endgroup\$ Jun 22, 2016 at 7:40
  • \$\begingroup\$ @JuliePelletier GCD is allowed because calculating GCD is not the intended problem to be solved. Sure, it might bump up the byte counts on these answers, but it doesn't make the challenge better. I'll edit to clarify. \$\endgroup\$
    – jqkul
    Jun 22, 2016 at 7:44

44 Answers 44

14
\$\begingroup\$

Mathematica, 27 22 bytes

Range@#~GCD~#~Count~1&

An unnamed function that takes and returns an integer.

Not much to explain here, except that @ is prefix notation for function calls and ~...~ is (left-associative) infix notation, so the above is the same as:

Count[GCD[Range[#], #], 1] &
\$\endgroup\$
12
\$\begingroup\$

J, 9 bytes

(-~:)&.q:

This is based on the Jsoftware's essay on totient functions.

Given n = p1e1p2e2 ∙∙∙ pkek where pk is a prime factor of n, the totient function φ(n) = φ(p1e1) ∙ φ(p2e2) ∙∙∙ φ(pkek) = (p1 - 1) p1e1 - 1 ∙ (p2 - 1) p2e2 - 1 ∙∙∙ (pk - 1) pkek - 1.

Usage

   f =: (-~:)&.q:
   (,.f"0) 1 2 3 8 9 26 44 105
  1  1
  2  1
  3  2
  8  4
  9  6
 26 12
 44 20
105 48
   f 12345
6576

Explanation

(-~:)&.q:  Input: integer n
       q:  Prime decomposition. Get the prime factors whose product is n
(   )&     Operate on them
  ~:         Nub-sieve. Create a mask where 1 is the first occurrence
             of a unique value and 0 elsewhere
 -           Subtract elementwise between the prime factors and the mask
     &.q:  Perform the inverse of prime decomposition (Product of the values)
\$\endgroup\$
2
  • \$\begingroup\$ Use the fact that totient is multiplicative to make another solution in J using recursion :) \$\endgroup\$
    – Leaky Nun
    Jun 22, 2016 at 10:29
  • \$\begingroup\$ @LeakyNun I don't think there's an easy way to golf the factoring, since even using the iterative form [:*/@({.(^-(^<:)){:)2&p: needs 24 bytes, even using the builtin to get the the primes and their exponents. Or maybe there's a shorter way and I don't see it. \$\endgroup\$
    – miles
    Jun 22, 2016 at 10:59
11
\$\begingroup\$

MATL, 7 bytes

t:Zd1=s

You can TryItOnline. Simplest idea, make a vector 1 to N, and taken gcd of each element with N (Zd does gcd). Then, find which elements are equal to 1, and sum the vector to get the answer.

\$\endgroup\$
1
  • \$\begingroup\$ The builtin is _Zp for those wondering. \$\endgroup\$
    – David
    Jun 22, 2016 at 8:01
9
\$\begingroup\$

Haskell, 28 bytes

f n=sum[1|1<-gcd n<$>[1..n]]

Uses Haskell's pattern matching of constants. The tricks here are fairly standard for golfing, but I'll explain to a general audience.

The expression gcd n<$>[1..n] maps gcd n onto [1..n]. In other words, it computes the gcd with n of each number from 1 to n:

[gcd n i|i<-[1..n]]

From here, the desired output is the number of 1 entries, but Haskell lacks a count function. The idiomatic way to filter to keep only 1's, and take the resulting length, which is much is too long for golfing.

Instead, the filter is simulated by a list comprehension [1|1<-l] with the resulting list l. Usually, list comprehensions bind values onto variable like in [x*x|x<-l], but Haskell allows a pattern to be matched against, in this case the constant 1.

So, [1|1<-l] generating a 1 on each match of 1, effectively extracting just the 1's of the original list. Calling sum on it gives its length.

\$\endgroup\$
2
  • \$\begingroup\$ I think this is the first Haskell answer I actually understand. It's such a cool language, but it's so different from most others. \$\endgroup\$
    – jqkul
    Jun 23, 2016 at 7:17
  • 1
    \$\begingroup\$ Wow, I expected that pattern matching had to be exhaustive in comprehension lists. Thanks for the trick. \$\endgroup\$
    – Damien
    Jun 23, 2016 at 8:54
9
\$\begingroup\$

Python 2, 44 bytes

f=lambda n,d=1:d/n or-f(d)*(n%d<1)-~f(n,d+1)

Less golfed:

f=lambda n:n-sum(f(d)for d in range(1,n)if n%d<1)

Uses the formula that the Euler totients of the divisors of n have a sum of n:

enter image description here

The value of ϕ(n) can then be recursively computed as n minus the sum over nontrivial divisors. Effectively, this is doing Möbius inversion on the identity function. I used the same method in a golf to compute the Möbius function.

Thanks to Dennis for saving 1 byte with a better base case, spreading the initial value of +n into +1 for each of the n loops, done as -~.

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

Jelly, 4 bytes

Rgċ1

Try it online!

Explanation

Rgċ1   Main monadic chain. Argument: z

R      Yield [1 2 3 .. z].
 g     gcd (of each) (with z).
  ċ1   Count the number of occurrences of 1.

With built-in

ÆṪ

Try it online!

Explanation

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.
\$\endgroup\$
7
+150
\$\begingroup\$

Regex (ECMAScript), 131 bytes

At least -12 bytes thanks to Deadcode (in chat)

(?=((xx+)(?=\2+$)|x+)+)(?=((x*?)(?=\1*$)(?=(\4xx+?)(\5*(?!(xx+)\7+$)\5)?$)(?=((x*)(?=\5\9*$)x)(\8*)$)x*(?=(?=\5$)\1|\5\10)x)+)\10|x

Try it online!

Output is the length of the match.

ECMAScript regexes make it extremely hard to count anything. Any backref defined outside a loop will be constant during the loop, any backref defined inside a loop will be reset when looping. Thus, the only way to carry state across loop iterations is using the current match position. That’s a single integer, and it can only decrease (well, the position increases, but the length of the tail decreases, and that’s what we can do math to).

Given those restrictions, simply counting coprime numbers seems impossible. Instead, we use Euler’s formula to compute the totient.

Here’s how it looks like in pseudocode:

N = input
Z = largest prime factor of N
P = 0

do:
   P = smallest number > P that’s a prime factor of N
   N = N - (N / P)
while P != Z

return N

There are two dubious things about this.

First, we don’t save the input, only the current product, so how can we get to the prime factors of the input? The trick is that (N - (N / P)) has the same prime factors > P as N. It may gain new prime factors < P, but we ignore those anyway. Note that this only works because we iterate over the prime factors from smallest to greatest, going the other way would fail.

Second, we have to remember two numbers across loop iterations (P and N, Z doesn’t count since it’s constant), and I just said that was impossible! Thankfully, we can swizzle those two numbers in a single one. Note that, at the start of the loop, N will always be a multiple of Z, while P will always be less than Z. Thus, we can just remember N + P, and extract P with a modulo.

Here’s the slightly more detailed pseudo-code:

N = input
Z = largest prime factor of N

do:
   P = N % Z
   N = N - P
   P = smallest number > P that’s a prime factor of N
   N = N - (N / P) + P
while P != Z

return N - Z

And here’s the commented regex:

# \1 = largest prime factor of N
# Computed by repeatedly dividing N by its smallest factor
(?= ( (xx+) (?=\2+$) | x+ )+ )

(?=
        # Main loop!
        (
                # \4 = N % \1, N -= \4
                (x*?) (?=\1*$)

                # \5 = next prime factor of N
                (?= (\4xx+?) (\5* (?!(xx+)\7+$) \5)? $ )

                # \8 = N / \5, \9 = \8 - 1, \10 = N - \8
                (?= ((x*) (?=\5\9*$) x) (\8*) $ )

                x*
                (?=
                        # if \5 = \1, break.
                        (?=\5$) \1
                |
                        # else, N = (\5 - 1) + (N - B)
                        \5\10
                )
                x
        )+
) \10

And as a bonus…

Regex 🐝 (ECMAScript 2018, number of matches), 23 bytes

x(?<!^\1*(?=\1*$)(x+x))

Try it online!

Output is the number of matches. ECMAScript 2018 introduces variable-length look-behind (evaluated right-to-left), which makes it possible to simply count all numbers coprime with the input.

It turns out this is independently the same method used by Leaky Nun's Retina solution, and the regex is even the same length (and interchangeable). I'm leaving it here because it may be of interest that this method works in ECMAScript 2018 (and not just .NET).

                        # Implicitly iterate from the input to 0
x                       # Don’t match 0
 (?<!                 ) # Match iff there is no...
                 (x+x)  # integer >= 2...
         (?=\1*$)       # that divides the current number...
     ^\1*               # and also divides the input
\$\endgroup\$
6
\$\begingroup\$

Pyke, 5 bytes

m.H1/

Try it here!

count(map(gcd, range(input)), 1)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ So many Python derivatives.. I like this one though. Interesting premise. \$\endgroup\$
    – jqkul
    Jun 22, 2016 at 8:15
5
\$\begingroup\$

J, 11 bytes

+/@(1=+.)i.

Usage

>> f =: +/@(1=+.)i.
>> f 44
<< 20

where >> is STDIN and << is STDOUT.

Explanation

+/ @ ( 1 = +. ) i.
               │
   ┌───────────┴┐
 +/@(1=+.)      i.
   │
 ┌─┼──┐
+/ @ 1=+.
    ┌─┼─┐
    1 = +.

>> (i.) 44            NB. generate range
<< 0 1 2 3 4 ... 43
>> (+.i.) 44          NB. calculate gcd of each with input
<< 44 1 2 1 4 ... 1
>> ((1=+.)i.) 44      NB. then test if each is one (1 if yes, 0 if no)
<< 0 1 0 1 0 ... 1
>> (+/@(1=+.)i.) 44   NB. sum of all the tests
<< 20
\$\endgroup\$
2
  • \$\begingroup\$ How did you get the vertical tree representation? I thought it only produced horizontal. \$\endgroup\$
    – miles
    Jun 22, 2016 at 8:51
  • \$\begingroup\$ @miles I typed it myself. \$\endgroup\$
    – Leaky Nun
    Jun 22, 2016 at 9:01
5
\$\begingroup\$

Python >=3.5, 76 64 58 bytes

Thanks to LeakyNun for golfing off 12 (!) bytes.

Thanks to Sp3000 for golfing off 6 bytes.

import math
lambda n:sum(math.gcd(n,x)<2for x in range(n))

I love how readable Python is. This makes sense, even through the golfedness.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ lambda n:sum(gcd(n,x)<2for x in range(n)) \$\endgroup\$
    – Leaky Nun
    Jun 22, 2016 at 7:39
  • \$\begingroup\$ Oh, Python finally added gcd to the math module! I didn't know it. \$\endgroup\$
    – rubik
    Jun 23, 2016 at 13:24
5
\$\begingroup\$

Ruby, 32 bytes

->n{(1..n).count{|i|i.gcd(n)<2}}

a lambda that takes an integer n, and returns the counts of how many integers in the range (1..n) are coprime with n.

\$\endgroup\$
3
  • \$\begingroup\$ Hello, and welcome to PPCG! This is a great first post. \$\endgroup\$ Jun 23, 2016 at 18:43
  • \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! This is a great first solution, keep it up! \$\endgroup\$
    – jqkul
    Jun 23, 2016 at 18:43
  • \$\begingroup\$ Thanks, not really that short, I wonder if it's possible to improve it. \$\endgroup\$ Jun 23, 2016 at 18:54
4
\$\begingroup\$

Perl 6,  26 24  22 bytes

{[+] (^$^n Xgcd $n) X== 1}
{+grep 2>*,(^$_ Xgcd$_)}
{[+] 2 X>(^$_ Xgcd$_)}

Explanation:

{
  [+] # reduce using &infix:<+>
    2
    X[>] # crossed compared using &infix:«>»
    (
      ^$_    # up to the input ( excludes input )
      X[gcd] # crossed using &infix:<gcd>
      $_     # the input
    )
}

Example:

#! /usr/bin/env perl6
use v6.c;

my &φ = {[+] 2 X>(^$_ Xgcd$_)};

say φ(1) # 1
say φ(2) # 1
say φ(3) # 2
say φ(8) # 4
say φ(9) # 6
say φ(26) # 12
say φ(44) # 20
say φ(105) # 48

say φ 12345 # 6576
\$\endgroup\$
1
  • \$\begingroup\$ 20 bytes \$\endgroup\$
    – Jo King
    Feb 23, 2019 at 8:20
4
\$\begingroup\$

Brachylog, 25 bytes

:{:1e.$pdL,?$pd:LcCdC}fl.

Explanation

Brachylog has no GCD built-in yet, so we check that the two numbers have no prime factors in common.

  • Main predicate:

    :{...}fl.             Find all variables which satisfy predicate 1 when given to it as
                          output and with Input as input.
                          Unify the Output with the length of the resulting list
    
  • Predicate 1:

    :1e.                  Unify Output with a number between Input and 1
        $pdL              L is the list of prime factors of Output with no duplicates
            ,
             ?$pd:LcC     C is the concatenation of the list of prime factors of Input with
                          no duplicates and of L
                     dC   C with duplicates removed is still C
    
\$\endgroup\$
4
\$\begingroup\$

Python 2, 57 bytes

f=lambda n,k=1,m=1:n*(k>n)or f(n-(n%k<m%k)*n/k,k+1,m*k*k)

Test it on Ideone.

Background

By Euler's product formula,

Euler's product formula

where φ denotes Euler's totient function and p varies only over prime numbers.

To identify primes, we use a corollary of Wilson's theorem:

corollary of Wilson's theorem

How it works

At all times, the variable m will be equal to the square of the factorial of k - 1. In fact, we named arguments default to k = 1 and m = 0!2 = 1.

As long as k ≤ n, n*(k>n) evaluates to 0 and the code following or gets executed.

Recall that m%k will yield 1 if m is prime and 0 if not. This means that x%k<m%k will yield True if and only if both k is a prime number and x is divisible by k.

In this case, (n%k<m%k)*n/k yields n / k, and subtracting it from n replaces its previous value with n(1 - 1/k), as in Euler's product formula. Otherwise, (n%k<m%k)*n/k yields 0 and n remains unchanged.

After computing the above, we increment k and multiply m by the "old" value of k2, thus maintaining the desired relation between k and m, then call f recursively with the updated arguments.

Once k exceeds n, n*(k>n) evaluates to n, which is returned by the function.

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

Python 2, 44 bytes

lambda n:sum(k/n*k%n>n-2for k in range(n*n))

This uses the same method to identify coprimes as my answer to “Coprimes up to N”.

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ With, I see, the slight adjustment of checking for a product of n-1 instead of 1, which makes it work for n==1. \$\endgroup\$ Feb 23, 2019 at 0:49
4
\$\begingroup\$

Julia 1.x, 22 bytes

!n=sum(gcd.(1:n,n).<2)

This is the same as the old solution, but using newer features of the language, as the original solution dates back to something like Julia 0.4. This solution uses function broadcasting to achieve the result more efficiently.


Julia, 25 bytes

!n=sum(i->gcd(i,n)<2,1:n)

It's simple - the sum function allows you to give it a function to apply before summing - basically the equivalent of running map and then sum. This directly counts the number of relatively prime numbers less than n.

\$\endgroup\$
1
  • \$\begingroup\$ this works in Julia 1.0, you can use TIO Try it online! \$\endgroup\$
    – MarcMush
    Jun 23, 2021 at 15:20
3
\$\begingroup\$

Pyth, 6 bytes

smq1iQ

Try it online!

/iLQQ1

Try it online!

Explanation

smq1iQ     input as Q
smq1iQdQ   implicitly fill variables

 m     Q   for d in [0 1 2 3 .. Q-1]:
    iQd        gcd of Q and d
  q1           equals 1? (1 if yes, 0 if no)
s          sum of the results


/iLQQ1     input as Q

 iLQQ      gcd of each in [0 1 2 3 .. Q-1] with Q
/    1     count the number of occurrences of 1
\$\endgroup\$
3
\$\begingroup\$

PowerShell v2+, 72 bytes

param($n)1..$n|%{$a=$_;$b=$n;while($b){$a,$b=$b,($a%$b)};$o+=!($a-1)};$o

PowerShell doesn't have a GCD function available to it, so I had to roll my own.

This takes input $n, then ranges from 1 to $n and pipes those into a loop |%{...}. Each iteration we set two helper variables $a and $b and then execute a GCD while loop. Each iteration we're checking that $b is still non-zero, and then saving $a%$b to $b and the previous value of $b to $a for the next loop. We then accumulate whether $a is equal to 1 in our output variable $o. Once the for loop is done, we place $o on the pipeline and output is implicit.

As an example of how the while loop works, consider $n=20 and we're on $_=8. The first check has $b=20, so we enter the loop. We first calculate $a%$b or 8%20 = 8, which gets set to $b at the same time that 20 gets set to $a. Check 8=0, and we enter the second iteration. We then calculate 20%8 = 4 and set that to $b, then set $a to 8. Check 4=0, and we enter the third iteration. We calculate 8%4 = 0 and set that to $b, then set $a to 4. Check 0=0 and we exit the loop, so the GCD(8,20) is $a = 4. Thus, !($a-1) = !(4-1) = !(3) = 0 so $o += 0 and we don't count that one.

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

Factor, 50 bytes

[ dup iota swap '[ _ gcd nip 1 = ] filter length ]

Makes a range (iota) n, and curries n into a function which gets gcd x n for all values of 0 <= x <= n, tests if the result is 1. Filter the original range on whether the result of gcd x n was 1, and take its length.

\$\endgroup\$
4
  • \$\begingroup\$ [ dup iota swap '[ _ gcd nip 1 = ] map sum ] saves 6 bytes (I think - not very experienced with Factor). \$\endgroup\$
    – jqkul
    Jun 24, 2016 at 1:49
  • \$\begingroup\$ @bkul Thanks for the suggestion! :D Unfortunately, there is no compatibility whatsoever between numbers and t/f (symbols) in Factor, so the only way to implement that would be with [ dup iota swap '[ _ gcd nip 1 = 1 0 ? ] map sum ], which is the same exact length as the current solution. \$\endgroup\$
    – cat
    Jun 24, 2016 at 1:58
  • \$\begingroup\$ Ah, dang. Strong typing strikes again. \$\endgroup\$
    – jqkul
    Jun 24, 2016 at 1:59
  • 1
    \$\begingroup\$ @bkul Well, I'm thankful for strong typing and TYPED: in real Factor code :P \$\endgroup\$
    – cat
    Jun 24, 2016 at 2:16
3
\$\begingroup\$

Japt -mx, 7 5 bytes

yN ¥1

Run it online

-2 bytes thanks to Shaggy

\$\endgroup\$
2
  • \$\begingroup\$ 5 bytes using -mx. \$\endgroup\$
    – Shaggy
    Feb 23, 2019 at 22:25
  • \$\begingroup\$ @Shaggy Ah, nice. I tried an -m solution but forgot about -x. Thanks! \$\endgroup\$
    – Oliver
    Feb 24, 2019 at 2:31
3
\$\begingroup\$

C (gcc), 67 65 bytes

f(x,a,b,y,z){for(z=y=x;a=y--;z-=b>1)for(b=x;a^=b^=a^=b%=a;);x=z;}

Try it online!

Edit: Removed temp variable.

Edit2: -1 thanks to @HowChen

Slightly less golfed

f(x,a,b,y,z){
  // counts y NOT coprime with x and subtract
  for(z=y=x;a=y--;z-=b>1)
    // compute GCD
    for(b=x;a^=b^=a^=b%=a;);
  x=z;
}
\$\endgroup\$
2
\$\begingroup\$

Retina, 36 29 bytes

7 bytes thanks to Martin Ender.

.+
$*
(?!(11+)\1*$(?<=^\1+)).

Try it online!

Explanation

There are two stages (commands).

First stage

.+
$*

It is a simple regex substitution, converting the input to that many ones.

For example, 5 would be converted to 11111.

Second stage

(?!(11+)\1*$(?<=^\1+)).

This regex tries to match the positions which satisfy the condition (co-prime with input), and then return the number of matches.

\$\endgroup\$
4
  • \$\begingroup\$ Lookbehind does not backtrack unless inside a lookahead? \$\endgroup\$
    – Leaky Nun
    Jun 22, 2016 at 9:47
  • \$\begingroup\$ Lookarounds don't backtrack in general. \$\endgroup\$ Jun 22, 2016 at 9:48
  • \$\begingroup\$ Then how is it that the regex tested every divisor? \$\endgroup\$
    – Leaky Nun
    Jun 22, 2016 at 9:48
  • 1
    \$\begingroup\$ Well they do backtrack as long as you don't leave them. As long as the engine is inside the lookaround it will try everything possible to make that lookaround match (or fail in the case of a negative lookaround). But once the lookaround is passed, the engine will not backtrack into it if anything after it fails (unless it then also starts to backtrack things in front of the lookaround and has to reevaluate everything anyway). \$\endgroup\$ Jun 22, 2016 at 9:50
2
\$\begingroup\$

05AB1E, 7 bytes

Lvy¹¿i¼

Explained

Lv        # for each x in range(1,n)
  y¹¿     # GCD(x,n)
     i¼   # if true (1), increase counter
          # implicitly display counter

Try it online

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

Common Lisp, 58 bytes

(defun o(x)(loop for i from 1 to x if (=(gcd x i)1)sum 1))

This is a simple loop which counts up 1 to the given n and increments the sum if gcd = 1. I use the function name o since t is the true boolean value. Not nearly the shortest but fairly simple.

\$\endgroup\$
1
  • \$\begingroup\$ Does CL not have some sort of anonymous function? \$\endgroup\$
    – cat
    Jun 23, 2016 at 22:17
2
\$\begingroup\$

MATLAB / Octave, 21 bytes

@(n)sum(gcd(n,1:n)<2)

Creates an anonymous function named ans which can be called with the integer n as the only input: ans(n)

Online Demo

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

APL, 7 bytes

+/1=⊢∨⍳

This is a monadic function train that takes an integer on the right. The approach here is the obvious one: sum (+/) the number of times the GCD of the input and the numbers from 1 to the input (⊢∨⍳) is equal to 1 (1=).

Try it here

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

Haskell, 31 30 bytes

\n->sum[1|x<-[1..n],gcd n x<2]

1 byte saved, thanks to @Damien.

Selects values with gcd = 1, maps each to 1, then takes the sum.

\$\endgroup\$
1
  • \$\begingroup\$ You can replace ==1 by <2 \$\endgroup\$
    – Damien
    Jun 23, 2016 at 6:20
2
\$\begingroup\$

JavaScript (ES6), 53 bytes

f=(n,k=n)=>k--&&(C=(a,b)=>b?C(b,a%b):a<2)(n,k)+f(n,k)

Try it online!

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

Brachylog v2, 16 bytes

{>ℕ≜;?ḋˢ{⊇ᵛ!}Ė}ᶜ

Try it online!

{             }ᶜ    Count the number of possible ways that:
  ℕ≜                some non-negative integer
 >                  less than the input
    ;?              and the input
      ḋˢ            have prime factorizations
        {⊇ᵛ!}       the largest shared subset of which
             Ė      is empty.

Brachylog v2, 16 bytes

⟨⟦₅zg⟩{ḋˢ⊇ᵛ!Ė}ˢl

Try it online!

   z                Cycling zip
 ⟦₅                 the range from 0 to one less than the input
⟨   g⟩              with a list containing only the input.
      {      }ˢ     Map where possible over the pairs:
       ḋˢ           the prime factorizations'
         ⊇ᵛ!        largest shared subset
            Ė       is empty.
               l    For how many pairs did it succeed?

A nuance that my explanations fail to capture is that fails given an input of 1, so if ḋˢ is given a list containing 1, the 1 is essentially discarded and ignored--so the ⊇ᵛ! (which is really "find any common subset, then discard all of this predicate's choice points", hence the braces in the first solution) of the remaining single number is its entire prime factorization, decidedly not empty, unless the list was nothing but 1s in which case everything is empty.

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

Husk, 7 bytes

ṁo=1⌋¹ḣ

Try it online!

ṁo=1⌋¹ḣ
ṁ     ḣ     # sum of function applied to 1..input
 o          # join 2 functions:
    ⌋¹      # greatest common divisor with input
  =1        # equals 1
\$\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.