Code-Challenge: Farey sequence (II)

Challenge

In this task you would be given an integer N (less than 10^6), output the number of terms in the Farey sequence of order N.

The input N < 106 is given in a single line, the inputs are terminated by EOF.

The challenge is to implement the fastest solution so that it can process a maximum of 106-1 values as fast as possible.

Input

7
10
999
9999
79000
123000

Output

19
33
303793
30393487
1897046599
4598679951

Constraints

• You can use any language of your choice
• Take care about your fingers, do not use more than 4096 bytes of code.
• Fastest solution, based on the running time measured for N = 106-1.
• Are you going to be timing each single submission in the same environment?! – J B Mar 30 '11 at 15:26
• @J B:I guess the complexity only can do the trick,checking each submission in the same environment will probably give the same result. – Quixotic Mar 30 '11 at 15:29
• The complexity can be O(1) because the input size is limited so we can pre-compute a lookup table... – Peter Taylor Mar 31 '11 at 12:18
• @Peter Taylor:Thanks,for pointing that out,I have updated the constraints. – Quixotic Mar 31 '11 at 15:43

C - 0.1 Secs on Ideone

http://www.ideone.com/E3S2t

Explanation included in code.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long A={0};
int main()
{
int isprime,d,n,k,i,e,p;

for (n=2;n<1001;n++)
isprime[n]=1;

//Sieve of Eratosthenes for Prime
//Storing the smallest prime which divides n.
//If A[n]=0 it means it is prime number.
for(d=2;d<1001;d++)
{
if(isprime[d])
{
for (n=d*d;n<1001;n+=d)
{
isprime[n]=0;
A[n]=d;
}
for (;n<=1000000;n+=d)
A[n]=d;
}
}

//Uses multiplicative property of
//Euler Totient Function
//Phi(n)=Phi(p1^k1)*Phi(p2^k2)...*Phi(pr^kr)
//and Phi(pi^ki)=(pi-1)*(pi^(ki-1))
A=1;
for(n=2;n<=1000000;n++)
{
if (A[n]==0)
A[n]=n-1;
else
{
p=A[n],k=n/p,e=1;
while (k%p==0)
k/=p,e*=p;
A[n]=A[k]*e*(p-1);
}
}
//Number of terms in Farey Series
//|F(n)| = 1 + Sigma(i,1,n,phi(i))
A=2;
for(n=2;n<=1000000;n++)
A[n]+=A[n-1];

while (~scanf("%d",&i))
printf("%lld\n",A[i]);
return 0;
}

A little more explanation:

For all numbers we get a prime factor of it from the sieve(or 0 if it is a prime). Next we use the fact that ETF is multiplicative. That is if m and n are coprime then phi(m*n)=phi(m)*phi(n). Here we take out the multiple of prime factor out and hence the left part and the multiple part are co-prime. We already have the ETF for the left part since it is either smaller then current value or equal to 1. We only need to calculate the ETF for the multiple which we calculate using the formula phi(pi^ki)=(pi-1)*(pi^(ki-1)).

• Between,you approach is slight faster than mine ... would you like to elaborate the implementation,precisely the ETF computation part,theoretically I understand though. – Quixotic Mar 31 '11 at 11:37
• Ah yes, of course, individual prime factorization like I did is a waste of time. – aaaaaaaaaaaa Mar 31 '11 at 11:46

C (0.2 sec in Ideone)

I thought of adding my approach too: (this is not as fast as Gaurav's)

#include <stdio.h>
#define N 1000000
long long Phi[N+1];

//Sieve ETF

int main(){
int i,j;

for(i=1;i<=N;i++)
Phi[i]=i;

for(i=2;i<=N;i++){
if(Phi[i] == i)
for(j=i;j<=N;j+=i)
Phi[j] = (Phi[j]/i)*(i-1);
}

int t,n;

Phi=2;
for(i = 2; i < N; i++)
Phi[i] += Phi[i-1];

for(;~scanf("%d",&n);)
printf("%lld\n",Phi[n]);

return 0;
}

TESTING ...

C - Less than a second for 999999

#include "stdio.h"
#include "time.h"
#define i64 unsigned long long
#define i32 unsigned int
#define PLIM 1100
#define FLIM 1000000

i32 primes[PLIM];
i64 f[FLIM];

int main(int argc, char *argv[]){
i64 start=clock();
i32 primesindex=0;
f=1;
f=2;
i32 a,b,c;
i32 notprime;
//Make a list of primes
for(a=2;a<PLIM;a++){
notprime=0;
for(b=0;b<primesindex;b++){
if(!(a%primes[b])){
notprime=1;
}
}
if(!notprime){
primes[primesindex]=a;
primesindex++;
}
}
i32 count,divided;
i32 nextjump=4;
i32 modlimit=2;
i32 invalue;
a=2;
for(c=1;c<argc;c++){
invalue=atoi(argv[c]);
if(invalue<FLIM && invalue){
//For each number from a to invalue find the totient by prime factorization
for(;a<=invalue;a++){
count=a;
divided=a;
b=0;
while(primes[b]<=modlimit){
if(!(divided%primes[b])){
divided/=primes[b];
//Adjust the count when a prime factor is found
count=(count/primes[b])*(primes[b]-1);
//Discard duplicate prime factors
while(!(divided%primes[b])){
divided/=primes[b];
}
}
b++;
}
//Adjust for the remaining prime, if one is there
if(divided>1){
count=(count/divided)*(divided-1);
}
//Summarize with the previous totients
f[a]=f[a-1]+(i64)count;
//Adjust the limit for prime search if needed
if(a==nextjump){
modlimit++;
nextjump=modlimit*modlimit;
}
}
//Output result
printf("%I64u\n",f[invalue]);
}
}
i64 end=clock();
//printf("Runtime: %I64u",end-start);
return 0;
}

This takes input from command line.

The computation is a simple sum of totients, it's only done once and only up to the biggest input.

Here is an Ideone version: http://www.ideone.com/jVbc0

• Just for the sake of competition Please elaborate your approach precisely the ETF computation and you may like to change a bit so that IDEONE testing could be done :-) – Quixotic Mar 31 '11 at 11:40
• The link doesn't work. – Erik the Outgolfer Feb 25 '18 at 12:28

VB.NET, 0.11 s for 10^6

This is basically a totient computation using prime sieve. The time is measured 10 times and the average is computed.

Module Module1

Sub Main()
Dim sw As New Stopwatch
Dim M As Integer = Console.ReadLine()
sw.Start()

Dim is_prime(M) As Integer
Dim phi(M) As Integer

For i = 0 To M
phi(i) = i
is_prime(i) = True
Next

For i = 2 To M
If is_prime(i) = True Then
phi(i) = i - 1
Dim j As Integer = 2 * i
Do Until j > M
is_prime(j) = False
phi(j) = phi(j) - (phi(j) / i)
j += i
Loop
End If
Next

Dim result As Long = 1
For i = 1 To M
result += phi(i)
Next

Console.WriteLine(result)
sw.Stop()
Console.WriteLine("Time Elasped : " & sw.ElapsedMilliseconds)
Dim a = Console.ReadLine()
End Sub

End Module
• Welcome to PPCG! – Martin Ender Feb 25 '18 at 11:10

J, 0.2s, short code

It feels weird to write ungolfed J, but it actually is the language for the task, for once.

input =: ". ;. _2 stdin ''
phi =: 5 & p:
max =: >. / input
acc_totient =: +/ \ phi >: i. max
output =: >: (<: input) { acc_totient
echo output

Reads input, constructs accumulated sum of totients up to the max, and reads output from there.

• Wow, for a second I thought that code might actually be readable, but the input line at least doesn't make any sense despite the result being stored in an appropriately named variable. :-P – aaaaaaaaaaaa Mar 31 '11 at 14:20
• @eBusiness: aww, c'mon ;) stdin '' reads and returns the entire input. ;. _2 applies the verb on its left to the argument on its right, split line by line. The verb on its left ". converts a string to a J noun, it our case a number. Would it be more readable to you as input =: ; do each cutLF stdin '' ? – J B Mar 31 '11 at 14:59
• I would,'t say that it's very clear, but using word commands does seem to make it look just a tad bit more familiar. – aaaaaaaaaaaa Mar 31 '11 at 16:52
• FWIW, I find it hugely less readable, but that's mostly because it does the same in a more convoluted way (unnecessary boxing and unboxing). Unfortunately, I couldn't find word commands for such simple actions. – J B Mar 31 '11 at 18:08