The matlab7 book I'm reading uses Durer's matrix as an example. This leads to my finding of the wiki page on magic squares. Sleek, or sick?
Another unrelated but similarly magical description on numbers encrypted in architectures:
Secrets In Plain Sight - Art, Architecture & Urban Design, and here on youtube.
Showing posts with label Number theory. Show all posts
Showing posts with label Number theory. Show all posts
Wednesday, August 15, 2012
Friday, April 9, 2010
Find prime numbers
There are many interesting results on this problem.
The naive method is testing odd factors up to n/2. It's O(n^2) though.
By eliminating multiples of 3, 5, 7 first you can eliminate about 70% of the numbers.
In testing, you can use square instead of square root to speed up calculation.
There are probabilistic algorithms, such as Rabin test, and Lehman test.
The Sieve of Atkin algorithm is described here. Cost is O((N/log) * log N) in time, and N^(1/2 + o(1)) in memory.
The sieve of Eratosthenes algorithm uses O(N) time and O(N^(1/2)(log (log N))/log N) memory.
BTW, the density of prime numbers around N is 1/ln(N). This translates to that the average gap between prime numbers around N is ln(N).
The naive method is testing odd factors up to n/2. It's O(n^2) though.
By eliminating multiples of 3, 5, 7 first you can eliminate about 70% of the numbers.
In testing, you can use square instead of square root to speed up calculation.
There are probabilistic algorithms, such as Rabin test, and Lehman test.
The Sieve of Atkin algorithm is described here. Cost is O((N/log) * log N) in time, and N^(1/2 + o(1)) in memory.
The sieve of Eratosthenes algorithm uses O(N) time and O(N^(1/2)(log (log N))/log N) memory.
BTW, the density of prime numbers around N is 1/ln(N). This translates to that the average gap between prime numbers around N is ln(N).
The Frobenius Number
This is a set of problems that ask for this: given a set of numbers S, find the minimal number that cannot be represented using linear combination of numbers in S.
Some results are:
1) if |S| = 1, then {1} is the only solution.
2) if |S| = 2, then for S = {a, b}, solution exists iff gcd(a, b) = 1, and the solution is a*b - a - b (James Joseph Sylvester, 1884). And the number of non-representable numbers in this case is (a-1)(b-1)/2.
3) if |S| = 3, algorithm exists to calculate the solution. One example is the McNugget number: you can buy McDonald's Chicken McNuggets in the pack of 6, 9 or 20, so S = {6, 9, 20}, the Frobenius number is 43:
44 = 6 + 9 + 9 + 20
45 = 9 + 9 + 9 + 9 + 9
46 = 6 + 20 + 20
47 = 9 + 9 + 9 + 20
48 = 6 + 6 + 9 + 9 + 9 + 9
49 = 9 + 20 + 20
Any number bigger can be obtained from these by adding a multiple of 6.
4) for general cases, it is proved to be NP-hard.
See here for an introduction to the Frobenius Number problem. Here is an extension of this problem into a set of strings and solution (2007).
Some results are:
1) if |S| = 1, then {1} is the only solution.
2) if |S| = 2, then for S = {a, b}, solution exists iff gcd(a, b) = 1, and the solution is a*b - a - b (James Joseph Sylvester, 1884). And the number of non-representable numbers in this case is (a-1)(b-1)/2.
3) if |S| = 3, algorithm exists to calculate the solution. One example is the McNugget number: you can buy McDonald's Chicken McNuggets in the pack of 6, 9 or 20, so S = {6, 9, 20}, the Frobenius number is 43:
44 = 6 + 9 + 9 + 20
45 = 9 + 9 + 9 + 9 + 9
46 = 6 + 20 + 20
47 = 9 + 9 + 9 + 20
48 = 6 + 6 + 9 + 9 + 9 + 9
49 = 9 + 20 + 20
Any number bigger can be obtained from these by adding a multiple of 6.
4) for general cases, it is proved to be NP-hard.
See here for an introduction to the Frobenius Number problem. Here is an extension of this problem into a set of strings and solution (2007).
Subscribe to:
Posts (Atom)