No, I don't mean \$\phi = 1.618...\$ and \$π = 3.14159...\$. I mean the functions.

  • \$\phi(x)\$ is the number of integers less than or equal to \$x\$ that are relatively prime to \$x\$.
  • \$π(x)\$ is the number of primes less than or equal to \$x\$.
  • Let's say that "not pi" is then \$\bar{\pi}(x)\$ and define it to be the number of composites less than or equal to \$x\$.


Given a strictly positive integer \$x\$, calculate \$\phi(\bar{\pi}(x))\$. Scoring is in bytes.


Each line consists of the input (from 1 to 100, inclusive) and the corresponding output separated by a space.

1 0 
2 0 
3 0 
4 1 
5 1 
6 1 
7 1 
8 2 
9 2 
10 4 
11 4 
12 2 
13 2 
14 6 
15 4 
16 6 
17 6 
18 4 
19 4 
20 10 
21 4 
22 12 
23 12 
24 6 
25 8 
26 8 
27 16 
28 6 
29 6 
30 18 
31 18 
32 8 
33 12 
34 10 
35 22 
36 8 
37 8 
38 20 
39 12 
40 18 
41 18 
42 12 
43 12 
44 28 
45 8 
46 30 
47 30 
48 16 
49 20 
50 16 
51 24 
52 12 
53 12 
54 36 
55 18 
56 24 
57 16 
58 40 
59 40 
60 12 
61 12 
62 42 
63 20 
64 24 
65 22 
66 46 
67 46 
68 16 
69 42 
70 20 
71 20 
72 32 
73 32 
74 24 
75 52 
76 18 
77 40 
78 24 
79 24 
80 36 
81 28 
82 58 
83 58 
84 16 
85 60 
86 30 
87 36 
88 32 
89 32 
90 48 
91 20 
92 66 
93 32 
94 44 
95 24 
96 70 
97 70 
98 24 
99 72 
100 36

Use this link to calculate the expected output for any input. Also, a list of inputs and outputs for \$x \le 1000\$ is provided here on pastebin. (Generated with this Minkolang program.)


Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=63710,OVERRIDE_USER=12914;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

  • 4
    \$\begingroup\$ Is this question a tribute to the user PhiNotPi? \$\endgroup\$
    – primo
    Commented Nov 13, 2015 at 4:52
  • 26
    \$\begingroup\$ @primo Why would you think that? \$\endgroup\$
    – user45941
    Commented Nov 13, 2015 at 4:59
  • 2
    \$\begingroup\$ @primo: It was inspired by his name, and definitely a pun on it, but not exactly a tribute to him. \$\endgroup\$ Commented Nov 13, 2015 at 5:41
  • 1
    \$\begingroup\$ @edc65: Yes, apparently so, as I found out yesterday. \$\endgroup\$ Commented Nov 13, 2015 at 9:52
  • 1
    \$\begingroup\$ @El'endiaStarman many people use a phone for PPCG and do not have a control key. \$\endgroup\$
    – Stan Strum
    Commented Oct 16, 2017 at 1:11

28 Answers 28


Regex (.NET), 122 113 bytes


Assuming input and output are in unary, and the output is taken from the main match of the regex.

Breakdown of the regex:

  • ^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*)) calculates π̅(x) and captures the rest of the string in capturing group 6 for assertion in the second part.

    • .*$ sets the pointer to the end of the string so that we have the whole number x in one direction.
    • (?<=^(\3+(.+.))(.*?(?>(.\4)?))) matches from right to left and checks for composite number by looping from x to 0.
      • (.*?(?>(.\4)?)) is a "variable" which starts from 0 in the first iteration and continues from the number in previous iteration and loops up to x. Since the smallest composite number is 4, (.\4)? never fails to match if capturing group 4 is available.
      • ^(\3+(.+.)) checks what is left by the "variable" above (i.e. x - "variable") whether it is a composite number.
  • ((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+ calculates φ(π̅(x)), by limiting the left-to-right operations with (?=\6$).

    • .*(?=\6$) sets the pointer to position π̅(x). Let's denote y = π̅(x).
    • (?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?))) matches from right to left and checks for relative prime by looping from (y - 1) to 0
      • (.+?(?>\9?)) is a "variable" which starts from 1 in the first iteration and continues from the number in previous iteration and loops up to y
      • (?!(.+.)\8*(?=\6$)(?<=^\8+)) matches from left to right 1 and checks whether the "variable" and y are relative prime.
        • (.+.)\8*(?=\6$) picks a divisor of "variable" which is larger than 1, and a side effect is that we have whole number y on the left.
        • (?<=^\8+) checks whether the divisor of "variable" is also the divisor of y.

1 In .NET, look-ahead sets the direction to LTR instead of following the current direction; look-behind sets the direction to RTL instead of reversing the direction.

Test the regex at RegexStorm.

Revision 2 drops non-capturing groups and uses atomic groups instead of conditional syntax.

  • 28
    \$\begingroup\$ Sir, you are mad. \$\endgroup\$
    – RK.
    Commented Nov 14, 2015 at 23:24
  • 10
    \$\begingroup\$ He's got a touch of the Zalgo I think. \$\endgroup\$ Commented Nov 15, 2015 at 13:02
  • 12
    \$\begingroup\$ And now you have two problems. (Seriously had no idea you could do this kind of thing with Regex...) \$\endgroup\$ Commented Nov 15, 2015 at 20:44

GS2, 12 10 bytes


The source code uses the CP437 encoding. Try it online!

Test run

$ xxd -r -ps <<< 564027116c2e3126136c > phinotpi.gs2
$ wc -c phinotpi.gs2 
10 phinotpi.gs2
$ gs2 phinotpi.gs2 <<< 1000

How it works

V          Read an integer n from STDIN.
 @         Push a copy of n.
  '        Increment the copy of n.
   ◄l      Push 1 and call primes; push the list of all primes below n+1.
     .     Count the primes.
      1    Subtract the count from n.
       &   Decrement to account for 1 (neither prime nor composite).
        ‼l Push 3 and call primes; apply Euler's totient function.
  • 29
    \$\begingroup\$ The file name is longer than the program. \$\endgroup\$
    – Floris
    Commented Nov 13, 2015 at 16:16

J, 15 14 bytes

5 p:<:-_1 p:>:

This is a tacit, monadic verb. Try it online with J.js.

How it works

                Right argument: y
            >:  Increment y.
       _1 p:    Calculate the number of primes less than y+1.
    <:          Decrement y.
      -         Calculate the difference of the results to the left and right.
5 p:            Apply Euler's totient function to the difference.
  • 15
    \$\begingroup\$ i can haz explanation? :P \$\endgroup\$ Commented Nov 13, 2015 at 0:19
  • 24
    \$\begingroup\$ i haz added explanation \$\endgroup\$
    – Dennis
    Commented Nov 13, 2015 at 0:57
  • 5
    \$\begingroup\$ I was about to say that I have upvoted this because it has lots of smileys, but the text told me to avoid those :( \$\endgroup\$
    – Doddy
    Commented Nov 13, 2015 at 10:13
  • \$\begingroup\$ @Dennis: Your first reply made me laugh pretty hard, thanks for that! \$\endgroup\$
    – user541686
    Commented Nov 14, 2015 at 22:48

Seriously, 27 bytes


Yay, I beat CJam! Try it online

Explanation (a refers to top of stack, b refers to second-from-top):

,;       take input and duplicate it
R`p`MΣ   push sum([is_prime(i) for i in [1,...,a]]) (otherwise known as the pi function)
(-D      rotate stack right by 1, subtract top two elements, subtract 1, push
            (@ could be used instead of (, but I was hoping the unmatched paren would bother someone)
;n;;     dupe top, push a b times, dupe top twice (effectively getting a a+1 times)
╟        pop n, pop n elements and append to list, push
@        swap top two elements
RZ       push [1,...,a], zip a and b
`ig1=`   define a function:
  i        flatten list
  g1=      compute gcd(a,b), compare to 1 (totient function)
MΣ       perform the function a on each element of b, sum and push

Note: since the posting of this answer, I have added the pi and phi functions to Seriously. Here is a noncompetitive answer with those functions:


Explanation (some commands are shifted to not overlap others):

,    get input (hereafter referred to as x)
;    duplicate x
 ▓   calculate pi(x) (we'll call this p)
1-   calculate 1-p
@-   bring x back on top, calculate x-1-p (not pi(x))
  ▒  calculate phi(not pi(x))
  • 1
    \$\begingroup\$ You have SERIOUSLY OUTGOLFED @Dennis ! \$\endgroup\$
    – TanMath
    Commented Nov 13, 2015 at 22:52
  • \$\begingroup\$ Please don't tell me you knew this at the top of your head.. \$\endgroup\$ Commented Nov 15, 2015 at 22:56
  • 1
    \$\begingroup\$ GJ beating CJam=) \$\endgroup\$
    – flawr
    Commented Nov 16, 2015 at 23:17

Julia, 52 50 bytes


This creates an unnamed function that accepts and integer and returns an integer. To call it, give it a name, e.g. f=x->....


function phinotpi(x::Integer)
    # The number of composites less than or equal to x is
    # x - the number of primes less than or equal to x -
    # 1, since 1 is not composite
    p = x - length(primes(x)) - 1

    # Return the number of integers i between 1 and p such
    # that gcd(i, p) = 1. This occurs when i is relatively
    # prime to p.
    count(i -> gcd(i, p) == 1, 1:p)
  • \$\begingroup\$ Use sum instead of count to save a couple of characters. It's a little frustrating, though - the other way to count the primes, sum(isprime,1:x), is exactly the same length as endof(primes(x)). \$\endgroup\$
    – Glen O
    Commented Nov 13, 2015 at 11:58
  • 1
    \$\begingroup\$ @GlenO Thanks for the suggestion, but sum fails for empty collections while count returns 0. Thus sum won't produce the desired result for x<4. \$\endgroup\$
    – Alex A.
    Commented Nov 13, 2015 at 20:48

Mathematica, 24 bytes

  • 2
    \$\begingroup\$ Of course Mathematica has all of this built in... \$\endgroup\$
    – clapp
    Commented Nov 16, 2015 at 16:23
  • \$\begingroup\$ @ConfusedMr_C Obviously :) However, it wasn't disqualified, for an obvious reason: mathematical software cannot beat golfing languges in simple combinatorial tasks :) \$\endgroup\$
    – yo'
    Commented Nov 17, 2015 at 8:05
  • \$\begingroup\$ @ConfusedMr_C PhiNotPi@#&: 11 bytes :P \$\endgroup\$ Commented Nov 17, 2015 at 11:34

Minkolang 0.11, 12 bytes (NOT competitive)

This answer is NOT competitive. I implemented pi and phi as built-ins before I posted the question, which gives me an unfair advantage. I post this only for those who are interested in the language.


Try it here.


n      Read in integer from input
d      Duplicate
9M     Pops off the top of stack as x and pushes pi(x)
-      Subtracts the top two elements on the stack (x - pi(x))
1-     Subtracts 1 (x-1 - pi(x))
9$M    Pops off the top of stack as x and pushes phi(x) (phi(x-1 - pi(x)))
N.     Outputs as integer and stops.
  • 2
    \$\begingroup\$ I don't think publishing invalid answers is a good idea... \$\endgroup\$
    – user19214
    Commented Nov 13, 2015 at 0:38
  • 21
    \$\begingroup\$ As long as they have a disclaimer, I don't think there's anything wrong with it. It's actually pretty common for older challenges. \$\endgroup\$
    – Dennis
    Commented Nov 13, 2015 at 0:41
  • 4
    \$\begingroup\$ @yeti: Technically, it's not invalid. The features used here were all implemented before the challenge was posted. I simply disqualify it because I delayed posting the challenge until two particular features were implemented (which I used to generate the example lists, incidentally). \$\endgroup\$ Commented Nov 13, 2015 at 0:44
  • 1
    \$\begingroup\$ Same. I do this a lot when 𝔼𝕊𝕄𝕚𝕟 keeps getting updated. \$\endgroup\$ Commented Nov 13, 2015 at 4:28

Pyth, 14 bytes


Demonstration, Verifier

We calculate composites using a simple filter, take its length, and save it to J. Then, we take the gcd of J with every number up to J, and count how many results equal 1.


CJam, 28 bytes


Try it this fiddle in the CJam interpreter or verify all test cases at once.

How it works

ri                            Read an integer N from STDIN.
  )                           Increment it. 
   {    },                    Filter; for each I in [0 ... N]:
    mf                          Push I's prime factorization.
      1>                        Discard the first prime.
                              If there are primes left, keep I.
          ,                   Count the kept integers. Result: C
           _,                 Push [0 ... C-1].
             f{          }    For each J in [0 ... C-1], push C and J; then:
               )                Increment J.
                {    }h         Do:
                 _                Push a copy of the topmost integer..
                  @               Rotate the integer below on top of it.
                   \%             Take that integer modulo the other integer.
                                If the residue is non-zero, repeat the loop.
                                This computes the GCD of C and J+1 using the
                                Euclidean algorithm.
                       )        Increment the 0 on the stack. This pushes 1.

                        =     Push 1 if the GCD is 1, 0 if not.
                          1b  Add all Booleans.
  • \$\begingroup\$ I tried the "verify all cases" link and got this: 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111. Is that right? \$\endgroup\$ Commented Nov 13, 2015 at 0:28
  • \$\begingroup\$ Yes, it checks that applying the code to the left column (input) equals the right column (output). \$\endgroup\$
    – Dennis
    Commented Nov 13, 2015 at 0:29
  • 5
    \$\begingroup\$ i can haz explanation on dis1? \$\endgroup\$ Commented Nov 13, 2015 at 1:04
  • 9
    \$\begingroup\$ @anOKsquirrel i haz explained dis1 2 \$\endgroup\$
    – Dennis
    Commented Nov 13, 2015 at 3:02
  • 5
    \$\begingroup\$ @Dennis kthxbai \$\endgroup\$ Commented Nov 13, 2015 at 12:39

Python, 137 139

print n,len([b for b in range(len([a for a in range(n)if not all(a%i for i in xrange(2,a))]))if all(b%i for i in xrange(2,b))])
  • 2
    \$\begingroup\$ I think you can save 2 bytes by removing the spaces between range(n) if and ])) if \$\endgroup\$
    – DankMemes
    Commented Nov 13, 2015 at 23:14
  • 3
    \$\begingroup\$ Given Python's relatively low Golf-ability (because of the whitespace requirements, etc.) this is pretty impressive! \$\endgroup\$
    – felixphew
    Commented Nov 15, 2015 at 1:20
  • \$\begingroup\$ @DankMemes, thanks for the tip! \$\endgroup\$
    – wnnmaw
    Commented Nov 16, 2015 at 14:47

Retina, 48 bytes


Try it online!



Convert input to unary.


Count composite numbers not greater than the input by counting how often we can match a string that consists of at least two repetitions of a factor of at least 2.


Convert to unary again.


Compute φ by counting from how many positions it is not possible to find a factor (of at least 2) of the suffix from that position which is also a factor of the prefix (if we do find such a factor then this i <= n shares a factor with n is therefore not coprime to it). The . at the end ensures that we don't count zero (for which we can't find a factor of at least 2).


Regex (.NET), 88 86 bytes


Try it online! (As a Retina program.)

Uses the same I/O as n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ 's answer, i.e. unary input and it matches a substring of the length of the result.

It might be possible to shorten this further by replacing one or both of the balancing groups with forward references.

Alternative at the same byte count:


There are also some alternatives for the first half, e.g. using a negative lookahead instead of a positive one for the compositive numbers, or using a conditional there as well.


I'll assume that you have a basic understanding of balancing groups, but in short, capturing groups in .NET are stacks (so each time you reuse the capturing group the new capture is pushed on top) and (?<-x>...) pops a capture from stack x. That's very helpful for counting things.

^                   # Only look at matches from the beginning of the input.
(?=                 # First, we'll compute the number of composites less than
                    # or equal to the input in group 2. This is done in a
                    # lookahead so that we don't actually advance the regex
                    # engine's position in the string.
  (                 #   Iterate through the input, one character at a time.
    (?=(..+)\2+$)?  #     Try to match the remainder of the input as a
                    #     composite number. If so the (..+) will add one
                    #     one capture onto stack 2. Otherwise, this lookahead
                    #     is simply skipped.
(?=                 # It turns out to be more convienient to work with n minus
                    # the number of composites less than or equal to n, and to
                    # have that a single backreference instead of the depth of
                    # a stack.
  (?<-2>.)*         #   Match one character for each composite we found.
  (.+)              #   Capture the remainder of the input in group 3.
(?=                 # Now we compute the totient function. The basic idea is
                    # similar to how we computed the number of composites,
                    # but there are a few differences.
                    # a) Of course the regex is different. However, this one
                    #    is more easily expressed as a negative lookahead (i.e.
                    #    check that the values don't share a factor), so this
                    #    won't leave a capture on the corresponding stack. We
                    #    fix this by wrapping the lookahead itself in a group
                    #    and making the entire group optional.
                    # b) We only want to search up the number of composites,
                    #    not up to the input. We do this by asserting that we
                    #    can still match our backreference \3 from earlier.

  (                 #   Iterate through the input, one character at a time.
    ((?!            #     Try not to match a number that shares a factor with
                    #     the number of composites, and if so push a capture
                    #     onto stack 5.
      (..+)\6*      #     Look for a factor that's at least 2...
      (?<=^\6+)     #     Make sure we can reach back to the input with that
                    #     factor...
      \3$           #     ...and that we're exactly at the end of the number
                    #     of composites.
  \3                #   Match group 3 again to make sure that we didn't look
                    #   further than the number of composites.
(?<-5>.)*           # Finally, match one character for each coprime number we
                    # found in the last lookahead.

PARI/GP, 27 bytes


Gaia, 5 bytes


Try it online!

ṗ⁈l(t   ~ Full program.

 ⁈      ~ Reject the elements that:
ṗ         ~ Are prime.
  l     ~ Length.
   (    ~ Decrement.
    t   ~ Euler's totient.

Jelly, 7 bytes


How it works

ÆC_@’ÆṪ  Input: n

ÆC       Count the primes less than or equal to n.
    ’    Yield n - 1.
  _@     Subtract the count from n - 1.
     ÆṪ  Apply Euler's totient function.

PARI/GP, 35 bytes


SageMath 26 bytes


Works well even for n=0 and n=1, thanks to Sage's implementation.


Jelly, 6 bytes


Try it online!

This is a collaboration between caird coinheringahhing and Mr. Xcoder in chat


_ÆC’ÆṪ   ~ Full program.

 ÆC      ~ Count the primes less than or equal to Z.
_        ~ Subtract from the input.
   ’     ~ Decrement.
    ÆṪ   ~ Euler's totient function.

Ohm v2, 7 bytes


Try it online!


Octave, 52 51


Edit: saved 1 byte thanks to Thomas Kwa


@(b)                                            # Define anonymous func with parameter b
  nnz(                                          # Count elements in φ(c)
    (                                           #
      d = [1:                                   # Create d= array of 1 to π̅(b)
            ( c = b - 1 - nnz(primes(b)) )      # Calculate c=π̅(b) by subtracting the
                                                #  number of elements in the array of prime
          ]                                     #  numbers from the number of ints in 2:b
    )(gcd(d, c) < 2)                            # Calculate φ(c) by using gcd to filter
  )                                             # relative primes from d

GAP, 33 Bytes


Number(l,p) counts how many elements from l satisfy p. To compensate for the fact that 1 is neither prime nor composite, I have to subtract from n one more than the number of primes up to n. Instead of doing -1 for two bytes, I start the list by -2 instead of 1 or 2, thus adding one more number that is considered prime by IsPrime for only one extra byte.


Python 3.5 - 130 bytes

from math import*
def p(n,k,g):
 for i in range(1,n+1):k+=factorial(i-1)%i!=i-1
 for l in range(1,k):g+=gcd(k,l)<2      
 return g

If it's not acceptable to pass the function through as p(n,0,0) then +3 bytes.

This takes advantage of the fact that I use Wilson's theorem to check if a number is composite and have to call into the math module for the factorial function. Python 3.5 added a gcd function into the math module.

The first loop of the code will increment k by one if the number is composite and increment by 0 else-wise. (Although Wilson's theorem only holds for integers greater than 1, it treats 1 as prime, so allows us to exploit this).

The second loop will then loop over the range of number of composites and increment g only when the value of not pi and l are co-prime.

g is then the number of values less than or equal to the number of composite numbers less than or equal to n.


Python 3 + sympy, 59 58 bytes

*-1 byte by replacing compositepi(k) with k+~primepi(k).

lambda k:totient(k+~primepi(k))
from sympy.ntheory import*

Try it online!


MATL, 9 bytes


Uses version (10.1.0) of the language/compiler.

Try it online!


:       % implicitly input a number "N" and produce array [1,2,...,N]
Zp      % true for entries that are prime
~       % negate. So it gives true for entries of [1,2,...,N] that are non-prime
s       % sum elements of array. So it gives number of non-primes
q       % subtract 1. Needed because number 1 is not prime, but not composite either
_       % unary minus
Zp      % with negative input, computes totient function of absolute value of input
        % implicit display

Pyt, 6 bytes



                Implicit input
ř               Push [1,2,...,input]
 ṗ              [is 1 prime?, is 2 prime?, ..., is input prime?]
  ¬             [is 1 not prime?, is 2 not prime?, ... is input not prime?]
   Ʃ            Number of non-primes (sums the array - booleans implicitly converted to ints)
    ⁻           Subtract one to remove the counting of '1'
     Ț          Euler's totient function

Try it online!


APL NARS, 38 bytes, 19 chars


13π is the totient function and 2π is the count prime function<= its argument. Test

1 0  2 0  3 0  4 1  5 1  6 1  7 1  8 2  9 2  10 4  11 4  12 2 
95 24  96 70  97 70  98 24  99 72  100 36

Add++, 21 bytes


Try it online!

How it works

This simply implements \$\overline\pi(n)\$ and \$\varphi(n)\$ without using the two explicit functions (mainly because they aren't builtin). The code can therefore be split into two sections: \$\overline\pi(n)\$ and \$\varphi(n)\$.



Here, operating on the input directly, we generate a range from [0 .. n] with R, then remove any primes with þP (filter false (þ) prime elements (P)). Unfortunately, this doesn't remove 1, as it isn't prime. Therefore, after taking the number of elements left with bL, we decrement once 1_ to remove the count for 1. This leaves \$x = \overline\pi(n)\$ on the stack.



This one is rather longer, due once again to 1. First, we duplicate \$x\$ and create a range to operate over with dR. Next, we save a copy of this range for a check we'll address later. Then, using filter true Þ%, we remove any elements that divide \$x\$, or keep any elements that have a GCD of 1 with \$x\$. Finally, we take the length of this list with bL.

Unfortunately, this yields 0 when the result should be 0 and \$n - 1\$ when the correct result is \$n\$. In order to fix this discrepancy, we retrieve the saved range with G, and convert it into a boolean value with !!. This makes empty ranges (which would yield 0) into 0 and every other range into 1. Finally, we add this value to our previous result and return it.

Yes, I did really want to try the new LaTex


05AB1E, 11 8 bytes


Try it online!

How it works

L             # this gets us the list of numbers [1 .. a]
 D            # duplicates this list
  p           # applies isPrime to each element of the list, vectorised.
   È          # is the element even? (does 05AB1E not have a logical not?)
    Ï         # push elements of the first list where the same index in the 
              # second list is 1
     g<       # finds the length and subtracts 1 (as the list contains 1)
              # this is the not pi function
       Õ      # euler totient function

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.