CS 100: Section Assignment S2

Solutions

// S2_1  Confirm that the next integer beyond (sqrt(3)+1)^(2n)	is
//       divisible by 2^(n+1).

import java.io.*;
public class S2_1
{
	public static void main(String args[])
	{
            int	n; 
	    double x;        // (sqrt(3)+1)^(2n)  
	    long xNext;      // ceil(x)     
	    long twoPower;   // 2^(n+1)
	    long rem;        // remainder when xNext is divided by twoPower
	    
	    TokenReader in = new TokenReader(System.in);
		
	    // Method 1
		
	    System.out.println("  n     (sqrt(3)+1)^(2n)        2^(n+1)    Remainder");
	    System.out.println("------------------------------------------------");
	    
	    
	    for (n=1;n<=15;n++)
	    {
			x =  Math.ceil(Math.pow(Math.sqrt(3.0)+1.0,2.0*n)); 
			xNext = (long) x;
			twoPower = (long) Math.pow( 2,n+1);    
			rem = xNext%twoPower;
			
			
			Format.print(System.out,"  %2d",n);
			Format.print(System.out,"  %20d",xNext);
			Format.print(System.out,"  %10d",twoPower);
			Format.println(System.out,"  %5d",rem);
	    }
	    
	    // Method 2
		
		final double factor = 4.0 + 2.0*Math.sqrt(3); // (sqrt(3)+1)*(sqrt(3)+1) = 4+2*sqrt(3)
		System.out.println("\n\n  n     (sqrt(3)+1)^(2n)        2^(n+1)    Remainder");
	        System.out.println("------------------------------------------------");
	    
	    
	        x = 1.0;
	        twoPower = 2;
	        for (n=1;n<=15;n++)
	        {
			x = x*factor  ;  
			xNext = (long) x+1;
			twoPower = 2*twoPower;    
			rem = xNext%twoPower;
			
			
			Format.print(System.out,"  %2d",n);
			Format.print(System.out,"  %20d",xNext);
			Format.print(System.out,"  %10d",twoPower);
			Format.println(System.out,"  %5d",rem);
	        }		
		// Wait for user to enter input to ensure console window remains visible
		in.waitUntilEnter();
	}
}

// S2_2: Trinkets

import java.io.*;
import java.awt.*;

public class CUCSDrawing extends Frame
{
    final int hc = 400;
    final int vc = 300;   // The circle center = (hc,vc).
	final int r1 = 200;   // The large circle radius.
	final int r2 = 20;    // The radius of the small circles.
	final int n  = 16;    // The number of pearls.
	
	public void paint(Graphics g)
	{
	
	    // -------------------------------
	    int h,v;        // (h,v) = center coordinates of the kth pearl.
	    double theta;   // The spacing angle 2pi/n.
	    int k;          // index
	    
		g.drawOval(hc-r1,vc-r1,2*r1,2*r1);    // Draw the circle.
		theta = 2*Math.PI/n;
		for (k=0;k<=n-1;k=k+1)
		{
		   h = (int)(hc + r1*Math.cos(k*theta));
		   v = (int)(vc - r1*Math.sin(k*theta));
		   if (k%2==0)
		   {
		      g.fillOval(h-r2,v-r2,2*r2,2*r2);
		   }
		   else
		   { 
		      g.fillRect(h-r2,v-r2,2*r2,2*r2);
		   }
		}
	   // --------------------------------------
    }
	
}

public class S2_2
{
	public static void main(String args[])
	{
		CUCSDrawing d = new CUCSDrawing();
		d.resize(1000,800);
		d.move(0,75);
		d.setTitle("S2_2");
		d.show();
		d.toFront();
	}
}

// S2_3  

import java.io.*;

public class S2_3
{
	
	public static void main(String args[])
	{
	        final int kmax=20;  // index of the last Fibonacci number printed
		int	k;          // index of the current Fibonacci number
		long z;         // the current Fibonacci number 
		long y;         // the "parent" of z.    
	        long x ;        // the "grandparent" of z.
	    
	        TokenReader in = new TokenReader(System.in);
		
		x = 0;
		y = 1;
		z = 1;
		for(k=1;k<=kmax;k=k+1)
		{
		   System.out.println("  " + k + "   " + z);
		   x = y;
		   y = z;
		   z = x + y;
	   
		}
		
		// Using a while loop...
		
		x = 0;
		y = 1;
		z = 1;
		k = 1;
		while (k<=kmax)
		{
		   System.out.println("  " + k + "   " + z);
		   x = y;
		   y = z;
		   z = x + y;
		   k = k+1;
	   
		}
		
		// Printing all Fibonacci numbers strictly less than a billion
		
	
	        x = 0;
		y = 1;
		z = 1;
		k = 1;
		while (z<=1000000000)
		{
		   System.out.println("  " + k + "   " + z);
		   x = y;
		   y = z;
		   z = x + y;
		   k = k+1;
	   
		}
	
	        in.waitUntilEnter();
	}

}

 

 // S2_4  Counting integers that have a specified property.

import java.io.*;

public class S2_4
{
	
	public static void main(String args[])
	{
	    TokenReader in = new TokenReader(System.in);
	    int k;              // Index
	    
	    
	    // A type A integer is not divisible by 2,3,5, or 7.
	    
	    int countA = 0;     // Keeps track of the number of type A integers.
	    for (k=1;k<=1000000;k=k+1)
	    {
	       if((k%2!=0) && (k%3!=0) && (k%5!=0) && (k%7!=0))
	       {
	          // k is not divisible by 2,3,5,or 7
	          // i.e., k is indivisible by 2 AND 3 AND 5 AND 7
	          countA = countA+1;
	       }
	    }
	    System.out.println("Number of type A numbers <= a million = " + countA);
	    
	    
	    // A type B integer has the property its one place value, its tens place value and
	    // its hundreds place value are not distinct. Thus, 9123 is not a type B integer but
	    // 17226 is.
	    
	    int countB = 0;     // Keeps track of the type B integers.
	    int U,T,H;          // For the ones, tens, and hundreds digit.
	    for (k=100;k<=999;k=k+1)
	    {
	       U = k%10;
	       T = (k/10)%10;
	       H = k/100;
	       if((U==T) || (U==H) || (H==T))
	       {
	          // The three digits that make up k are NOT distinct.
	          // i.e., Either U and T are the same  OR U and H are the same OR H and T are the same.
	          countB = countB+1;
	       }
	    }
	 
	    System.out.println("Number of type B numbers in the interval [100,999] = " + countB);
	    in.waitUntilEnter();
	}

}