CSCE 411 Lecture 1

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 $e$ }.com

Recall:

$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 $e$?
• How do we determine if a number is prime?

Digits of $e$

First approach: Use the fact that $\left(1+{\frac {1}{n}}\right)^{n}\leq e<\left(1+{\frac {1}{n}}\right)^{n+1}$

Too much work and requires arithmetic with large rational numbers.

Assuming that $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);

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

$a_{0}+{\frac {1}{2}}\left(a_{1}+{\frac {1}{3}}\left(a_{2}+{\frac {1}{4}}\left(\ldots \right)\right)\right)$

The digits $a_{i}$ are nonnegative integers, and by regularity, the $i$^th digit is supposed to be $i$ or less.

e.g. in base 10, each $a_{i}$ is in range 0–9, and each digits' place value is 10 × previous place.

Mixed radix representation of $e$ is (2; 1, 1, 1, 1, 1, …)

Multiplying the number by 10 is $(10a_{0};10a_{1},10a_{2},10a_{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,000^th digit?) Sure, just check how probable a number is to be prime.

Probability to be prime

Let $\pi \left(x\right)={\mbox{number of primes }}\leq 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}