CSCE 411 Lecture 1

From Notes
Jump to navigation Jump to search
Lecture Slides

« previous | Monday, August 27, 2012 | next »


Course Introduction

Quizzes, Homework, very important.

2 Exams: Midterm (Oct 8), Final (Dec 12 10:30–12:30)

Culture Reports

Motivation

{ first 10-digit prime found in consecutive digits of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} }.com

Recall:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e = \sum_{k=0}^\infty \frac{1}{k!} = \lim_{n\to\infty} \left(1+\frac{1}{n}\right)^n \approx 2.718\ldots}

Simple Algorithm: 

int* = // compute digits of e
int i = 0;
while(true) {
    int p = // extract 10-digit number at position i
    if (is_prime(p)) { 
        return p;
    }
    i++;
}

2 questions to solve:

  • How do we find digits of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} ?
  • How do we determine if a number is prime?

Digits of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e}

First approach: Use the fact that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( 1 + \frac{1}{n}\right)^n \le e < \left(1+\frac{1}{n}\right)^{n+1}}

Too much work and requires arithmetic with large rational numbers.

Assuming that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} has been computed perfectly, we can extract one digit at a time with 

d[0] = floor(e);
e1 = 10*(e-d[0]);
d[1] = floor(e1);
e2 = 10*(e1-d[1]);
d[2] = floor(e2);

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} is a transcendental number, so there is no pattern to number sin base 10

Use a mixed-radix representation that leads to a more regular pattern of the digits.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0 + \frac{1}{2} \left( a_1 + \frac{1}{3} \left( a_2 + \frac{1}{4} \left( \ldots \right) \right) \right)}

The digits Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i} are nonnegative integers, and by regularity, the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} th digit is supposed to be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} or less.

e.g. in base 10, each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i} is in range 0–9, and each digits' place value is 10 × previous place.

Mixed radix representation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} is (2; 1, 1, 1, 1, 1, …)

Multiplying the number by 10 is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (10 a_0; 10 a_1, 10 a_2, 10 a_3, \ldots)} , but this breaks the regularity.


Revisiting the Question

Could we get away with doing something lazily? (do we even need the 10,000,000th digit?) Sure, just check how probable a number is to be prime.

Probability to be prime

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi \left(x\right) = \mbox{number of primes } \le x}

The probability of a number with 10 digits is prime is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(99999 99999)/99999 99999 \approx 0.45}

The probability that none of the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} 10-digit numbers in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} are prime is roughly Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.955^k} ; quickly falls to 0

No need to recalculate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} , we just need the first few hundred digits.

Calculate primes using Sieve of Eratosthenes (knock out all multiples of integers 0 to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{x}} )

What was that all about?

The billboard was an ad paid for by Google, the website 7427466391.com contained another challenge and asked people to submit their résumé. This is not surprising since Google is obsessed with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e}

Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_411_Lecture_1&oldid=3284"