1 Sugar functions

  • A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, \(a^2 + b^2 = c^2\). For example, \(3^2 + 4^2 = 5^2\).
  • There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
// A Pythagorean triplet is a set of three natural numbers, a < b < c, 
// for which, a^2 + b^2 = c^2
// For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
// There exists exactly one Pythagorean triplet for which a + b + c = 1000.
// Find the product abc.
#include<stdio.h>
int Pythagorean(int n){
    int a,b,c,m=n/2;
    for(a=1;a<m;a++)
        for(b=a+1;b<m;b++)
            for(c=b+1;c<m;c++)
                if(a*a+b*b==c*c&&n==a+b+c)
                    printf("%d %d %d  %d\n",a,b,c,a*b*c);
return a*b*c;
}

int main(){
  int count;
    count = Pythagorean(1000);
    printf("abc=%d\n",count);
    return 0;
}
  • The following iterative sequence is defined for the set of positive integers: \[ \left\{ \begin{array}{ll} n \rightarrow n/2, & \hbox{if $n$ is even;} \\ n \rightarrow 3n+1, & \hbox{if $n$ is odd.} \end{array} \right. \] Using the rule above and starting with 13, we generate the following sequence: \[13 \rightarrow 40 \rightarrow20 \rightarrow10 \rightarrow5 \rightarrow16 \rightarrow8 \rightarrow4 \rightarrow2 \rightarrow1.\] It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
#include<stdio.h>
#define change(n) n%2?3*n+1:n/2
int chainLen(int n){
    int len=1;
    while(n>1){
        n = change(n);
        len++;
        printf("--> %d\t",n);
    }
    return len;
}
int main(){
    int n;
    printf("Input a natural number n = ");
    scanf("%d",&n);
    printf("%d\t",n);
    printf("\nThe length of chain is %d\n",chainLen(n));
    return 0;
}

or

#include<stdio.h>
#define change(n) n%2?3*n+1:n/2
int chainLen(int chain[], int n){
    int len=1;
    chain[0]=n;
    while(n>1){
        n = change(n);
        chain[len] = n;
        len++;
    }
    return len;
}
int main(){
    int n,i,len,chain[100]={0};
    printf("Input a natural number n = ");
    scanf("%d",&n);

    printf("\nThe length of chain is %d\n",len=chainLen(chain,n));
    printf("\n%d\t",chain[0]);
    for(i=1;i<len;i++) printf(" --> %d\t",chain[i]);
    return 0;
}

2 Arrays

2.1 Syntax

  • Example for the declaration of an array, int a[10]
  • Arrays as arguments of a function, int f(int a[])

2.2 Sugar functions

  • Sort 4 integers without arrays
#include <stdio.h>
void swap(int*a, int*b){
    int t;
    if(*a>*b){
        t=*a;
        *a=*b;
        *b=t;
    }
}
int main()
{
    int a,b,c,d;
    scanf("%d,%d,%d,%d",&a,&b,&c,&d);
    swap(&a,&b);
    swap(&b,&c);
    swap(&c,&d);
    swap(&a,&b);
    swap(&b,&c);
    swap(&a,&b);
    printf("%d,%d,%d,%d\n",a,b,c,d);
    return 0;
}
  • Sort 4 integers by using arrays
#include <stdio.h>
#define N 10
int main()
{
    int i,j,t,a[N];
    for(i=0;i<N;i++){
        a[i]=N-i;
        printf("%d\t",a[i]);
    }
    printf("\n");

    for(i=0;i<N-1;i++){
        for(j=0;j<N-i-1;j++){
            if(a[j]>a[j+1]){
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
        for(j=0;j<N;j++) printf("%d\t",a[j]);
        printf("\n");
    }
    return 0;
}

or

#include <stdio.h>
#define N 10
void swap(int*a, int*b){
    int t;
    t=*a;
    *a=*b;
    *b=t;
}

int main()
{
    int i,j,a[N];
    for(i=0;i<N;i++){
        a[i]=N-i;
        printf("%d\t",a[i]);
    }
    printf("\n");

    for(i=0;i<N-1;i++){
        for(j=0;j<N-i-1;j++)
            if(a[j]>a[j+1]) swap(&a[j],&a[j+1]);
        for(j=0;j<N;j++) printf("%d\t",a[j]);
        printf("\n");
    }
    return 0;
}
  • There are four towers with center (2,2), (-2,2), (-2,-2), and (2,-2), and radix 1 and highth 10. Tall us the highthof any inputted point in the plane.
  • Not using arrays:
#include<stdio.h>
int main()
{
    float x,y,d1,d2,d3,d4;
    int x1=2,y1=2,x2=-2,y2=2,x3=-2,y3=-2,x4=2,y4=-2;
    printf("Please input a point (x,y):");
    scanf("%f,%f",&x,&y);
    d1=(x-x1)*(x-x1)+(y-y1)*(y-y1);
    d2=(x-x2)*(x-x2)+(y-y2)*(y-y2);
    d3=(x-x3)*(x-x3)+(y-y3)*(y-y3);
    d4=(x-x4)*(x-x4)+(y-y4)*(y-y4);
    if (d1<=1||d2<=1||d3<=1||d4<=1)
        printf("h=10");
    else
        printf("h=0");
    return 0;
}
  • By using arrays
#include<stdio.h>
#define N 4
int main()
{
    float x1,y1,d,x[N],y[N];
    int i,flag=0;
    x[0]=2,y[0]=2,x[1]=-2,y[1]=2,x[2]=-2,y[2]=-2,x[3]=2,y[3]=-2;

    printf("Please input a point (x,y):");
    scanf("%f,%f",&x1,&y1);

    for(i=0;i<N;i++){
        d=(x1-x[i])*(x1-x[i])+(y1-y[i])*(y1-y[i]);
        if(d<=1){
            flag=1;
            break;
        }
    }
    if (flag)
        printf("h=10");
    else
        printf("h=0");
    return 0;
}

3 Problem in the previous week

  1. Calculate the sum of the even-valued terms of Fibonacci series. Starting with 1, 2, and 3.
#include <stdio.h>
#define N 4000000
int Fibonacci(int n){
    int f1=1, f2=2, f3=f1+f2, sum=2, count=0;
    while(f3<n){
        count++;
        if(count==3){
            count=0;
            sum+=f3;
        }
        f1=f2;
        f2=f3;
        f3=f1+f2;
    }
    return sum;
}

int main(){
    int sum;
    sum = Fibonacci(N);
    printf("sum = %d\n",sum);
    return 0;
}
  1. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
#include<stdio.h>
#include<math.h>
int isPrime(int n){
    int i=2;
    double sqrtn=sqrt(1.0*n);
    while(i<=sqrtn){
        if(!(n%i)) return 0;
        i++;
    }
    return 1;
}

int isDivededBy1toN(int n){
    int i=2,j;
    int m0,factor=1;
    for(i=2;i<=n;i++)
        if(isPrime(i)){
            m0=j=i;
            while((j*=i)<=n) m0 = j;
            factor *= m0;
            printf("j = %d\n",m0);
        }
    return factor;
}

int main(){
  int n;
    n = isDivededBy1toN(20);
    printf("n = %d\n",n);
    return 0;
}

or

#include<stdio.h>
#include<math.h>
int isPrime(int n){
    int i=2;
    double sqrtn=sqrt(1.0*n);
    while(i<=sqrtn){
        if(!(n%i)) return 0;
        i++;
    }
    return 1;
}

int isDivededBy1toN(int n){
    int a[100];
    int i=2,j,count=0;
    int m0,factor=1;

    for(i=2;i<=n;i++)
        if(isPrime(i)) a[count++]=i;

    //printf("a = \n");
    //for(i=0;i<count;i++) printf("%d\t",a[i]);
    //printf("\n");

    for(j=0;j<count;j++){
        m0=i=a[j];
        while((i*=a[j])<=n) m0 = i;
        factor *= m0;
        printf(" i = %d\n",m0);
    }
    return factor;
}

int main(){
  int n;
    n = isDivededBy1toN(20);
    printf("n = %d\n",n);
    return 0;
}
  • test if the above solution is correct
#include <stdio.h>
int main(){
    int i, count = 0, x=232792560;
    for(i=1;i<=20;i++){
        if(x%i==0){
            count++;
            printf("i = %d\n",i);
        }
    }
    printf("count = %d\n",count);
    return 0;
}
  • Further, what is the smallest positive number that is evenly divisible by all of the numbers from 1 to 40?
// solution 5342931457063200
#include<stdio.h>
#include<math.h>
#define N 40
int isPrime(int n){
    int i=2;
    double sqrtn=sqrt(1.0*n);
    while(i<=sqrtn){
        if(!(n%i)) return 0;
        i++;

    }
    return 1;
}

double isDivededBy1toN(int n){
    int i=2,j,m0;
    double factor=1.0;
    for(i=2;i<=n;i++)
        if(isPrime(i)){
            m0=j=i;
            while((j*=i)<=n) m0 = j;
            factor *= m0;
            printf("j=%d\n",m0);
        }
    return factor;
}

int main(){
    double n;
    int i;
    n = isDivededBy1toN(N);
    printf("n=%lf\n",n);
    for(i=N;i>0;i--){
        printf("i = %d,\t%lf\n",i,n/i);
    }
    return 0;
}

or

#include<stdio.h>
#include<math.h>
#define N 40
int isPrime(int n){
    int i=2;
    double sqrtn=sqrt(1.0*n);
    while(i<=sqrtn){
        if(!(n%i)) return 0;
        i++;

    }
    return 1;
}

long long isDivededBy1toN(int n){
    int i=2,j,m0;
    long long factor=1.0;
    for(i=2;i<=n;i++)
        if(isPrime(i)){
            m0=j=i;
            while((j*=i)<=n) m0 = j;
            factor *= m0;
            printf("j=%d\n",m0);
        }
    return factor;
}

int main(){
    long long n;
    int i;
    n = isDivededBy1toN(N);
    printf("n=%lld\n",n);
    for(i=N;i>0;i--){
        printf("i = %d,\t%lf\n",i,n/i);
    }
    return 0;
}

4 Problems

1 Calculate 1/2019 with 100-digit precesion and save them in an array (int or char). Print it with 10 digits per line.

2 More generally, what is the smallest positive number that is evenly divisible by all of the numbers from 1 to N? Here N could be large, such as 10000.