72
\$\begingroup\$

No, I don't mean ϕ = 1.618... and π = 3.14159.... I mean the functions.

  • φ(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 π̅(x) and define it to be the number of composites less than or equal to x.

Task

Given a strictly positive integer x, calculate φ(π̅(x)). Scoring is in bytes.

Examples

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 <= 1000 is provided here on pastebin. (Generated with this Minkolang program.)


Leaderboards

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>

\$\endgroup\$
  • \$\begingroup\$ Are there limits on the size of the input? \$\endgroup\$ – lirtosiast Nov 13 '15 at 0:30
  • 4
    \$\begingroup\$ Is this question a tribute to the user PhiNotPi? \$\endgroup\$ – primo Nov 13 '15 at 4:52
  • 24
    \$\begingroup\$ @primo Why would you think that? \$\endgroup\$ – Mego Nov 13 '15 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\$ – El'endia Starman Nov 13 '15 at 5:41
  • 1
    \$\begingroup\$ @edc65: Yes, apparently so, as I found out yesterday. \$\endgroup\$ – El'endia Starman Nov 13 '15 at 9:52

28 Answers 28

27
\$\begingroup\$

GS2, 12 10 bytes

V@'◄l.1&‼l

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
552

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.
\$\endgroup\$
  • 25
    \$\begingroup\$ The file name is longer than the program. \$\endgroup\$ – Floris Nov 13 '15 at 16:16
43
+50
\$\begingroup\$

Regex (.NET), 122 113 bytes

^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+

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.

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

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.
\$\endgroup\$
  • 14
    \$\begingroup\$ i can haz explanation? :P \$\endgroup\$ – anOKsquirrel Nov 13 '15 at 0:19
  • 23
    \$\begingroup\$ i haz added explanation \$\endgroup\$ – Dennis Nov 13 '15 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 Nov 13 '15 at 10:13
  • \$\begingroup\$ @Dennis: Your first reply made me laugh pretty hard, thanks for that! \$\endgroup\$ – Mehrdad Nov 14 '15 at 22:48
19
\$\begingroup\$

Seriously, 27 bytes

,;R`p`MΣ(-D;n;;╟@RZ`ig1=`MΣ

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:

,;▓1-@-▒

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ You have SERIOUSLY OUTGOLFED @Dennis ! \$\endgroup\$ – TanMath Nov 13 '15 at 22:52
  • \$\begingroup\$ Please don't tell me you knew this at the top of your head.. \$\endgroup\$ – DividedByZero Nov 15 '15 at 22:56
  • 1
    \$\begingroup\$ GJ beating CJam=) \$\endgroup\$ – flawr Nov 16 '15 at 23:17
14
\$\begingroup\$

Julia, 52 50 bytes

x->count(i->gcd(i,p)<2,1:(p=x-endof(primes(x))-1))

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

Ungolfed:

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)
end
\$\endgroup\$
  • \$\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 Nov 13 '15 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. Nov 13 '15 at 20:48
8
\$\begingroup\$

Mathematica, 24 bytes

EulerPhi[#-PrimePi@#-1]&
\$\endgroup\$
  • 2
    \$\begingroup\$ Of course Mathematica has all of this built in... \$\endgroup\$ – clap Nov 16 '15 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' Nov 17 '15 at 8:05
  • \$\begingroup\$ @ConfusedMr_C PhiNotPi@#&: 11 bytes :P \$\endgroup\$ – LegionMammal978 Nov 17 '15 at 11:34
8
\$\begingroup\$

Pyth, 14 bytes

JlftPTSQ/iLJJ1

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.

\$\endgroup\$
7
\$\begingroup\$

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.

nd9M-1-9$MN.

Try it here.

Explanation

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ I don't think publishing invalid answers is a good idea... \$\endgroup\$ – yeti Nov 13 '15 at 0:38
  • 20
    \$\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 Nov 13 '15 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\$ – El'endia Starman Nov 13 '15 at 0:44
  • 1
    \$\begingroup\$ Same. I do this a lot when 𝔼𝕊𝕄𝕚𝕟 keeps getting updated. \$\endgroup\$ – Mama Fun Roll Nov 13 '15 at 4:28
6
\$\begingroup\$

CJam, 28 bytes

ri){mf1>},,_,f{){_@\%}h)=}1b

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.
\$\endgroup\$
  • \$\begingroup\$ I tried the "verify all cases" link and got this: 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111. Is that right? \$\endgroup\$ – El'endia Starman Nov 13 '15 at 0:28
  • \$\begingroup\$ Yes, it checks that applying the code to the left column (input) equals the right column (output). \$\endgroup\$ – Dennis Nov 13 '15 at 0:29
  • 5
    \$\begingroup\$ i can haz explanation on dis1? \$\endgroup\$ – anOKsquirrel Nov 13 '15 at 1:04
  • 9
    \$\begingroup\$ @anOKsquirrel i haz explained dis1 2 \$\endgroup\$ – Dennis Nov 13 '15 at 3:02
  • 5
    \$\begingroup\$ @Dennis kthxbai \$\endgroup\$ – anOKsquirrel Nov 13 '15 at 12:39
5
\$\begingroup\$

Python, 137 139

n=input()
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))])
\$\endgroup\$
  • 2
    \$\begingroup\$ I think you can save 2 bytes by removing the spaces between range(n) if and ])) if \$\endgroup\$ – DankMemes Nov 13 '15 at 23:14
  • 3
    \$\begingroup\$ Given Python's relatively low Golf-ability (because of the whitespace requirements, etc.) this is pretty impressive! \$\endgroup\$ – felixphew Nov 15 '15 at 1:20
  • \$\begingroup\$ @DankMemes, thanks for the tip! \$\endgroup\$ – wnnmaw Nov 16 '15 at 14:47
5
\$\begingroup\$

Retina, 48 bytes

.+
$*
M&`(..+)\1+$
.+
$*
(?!(..+)\1*$(?<=^\1+)).

Try it online!

Explanation

.+
$*

Convert input to unary.

M&`(..+)\1+$

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.

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

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).

\$\endgroup\$
5
\$\begingroup\$

Regex (.NET), 88 86 bytes

^(?=((?=(..+)\2+$)?.)+)(?=(?<-2>.)*(.+))(?=(((?!(..+)\6*(?<=^\6+)\3$))?.)*\3)(?<-5>.)*

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:

^(?=((?=(..+)\2+$)?.)+)(?=(?<-2>.)*(.+))(?=(?((..+)\4*(?<=^\4+)\3$).|(.))*\3)(?<-5>.)*

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.

Explanation

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.
\$\endgroup\$
4
\$\begingroup\$

PARI/GP, 27 bytes

n->eulerphi(n-1-primepi(n))
\$\endgroup\$
3
\$\begingroup\$

Octave, 52 51

@(b)nnz((d=[1:(c=b-1-nnz(primes(b)))])(gcd(d,c)<2))

Edit: saved 1 byte thanks to Thomas Kwa

Explanation:

@(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
\$\endgroup\$
3
\$\begingroup\$

PARI/GP, 35 bytes

n->eulerphi(sum(x=2,n,!isprime(x)))
\$\endgroup\$
3
\$\begingroup\$

SageMath 26 bytes

euler_phi(n-1-prime_pi(n))

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

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

Jelly, non-competing

7 bytes This answer is non-competing, since it uses a language that postdates the challenge.

ÆC_@’ÆṪ

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.
\$\endgroup\$
3
\$\begingroup\$

Ohm v2, 7 bytes

³³Pl-‹φ

Try it online!

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

MATL, 9 bytes (non-competing)

This answer is non-competing, as the language postdates the challenge.

:Zp~sq_Zp

Uses version (10.1.0) of the language/compiler.

Try it online!

Explanation

:       % 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
\$\endgroup\$
2
\$\begingroup\$

GAP, 33 Bytes

n->Phi(n-Number([-2..n],IsPrime))

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.

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

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.

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

Jelly, 6 bytes

_ÆC’ÆṪ

Try it online!

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

Explanation

_ÆC’ÆṪ   ~ Full program.

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

Gaia, 5 bytes

ṗ⁈l(t

Try it online!

ṗ⁈l(t   ~ Full program.

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

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!

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

05AB1E, 11 8 bytes

LDpÈÏg<Õ

Try it online!

This might be non competing - I can't find out when 05AB1E was made.

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
\$\endgroup\$
1
\$\begingroup\$

Pyt, 6 bytes

řṗ¬Ʃ⁻Ț

Explanation:

                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!

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

APL NARS, 38 bytes, 19 chars

{⍵≤3:0⋄13π¯1+⍵-2π⍵}

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

  b←{⍵≤3:0⋄13π¯1+⍵-2π⍵}     
  (⍳12),¨b¨⍳12
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..100),¨b¨(95..100)
95 24  96 70  97 70  98 24  99 72  100 36
\$\endgroup\$
1
\$\begingroup\$

Add++, 21 bytes

L,RþPbL1_dRdVÞ%bLG!!+

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

\$\overline\pi(n)\$

RþPbL1_

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.

\$\varphi(n)\$

dRdVÞ%bLG!!+

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

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