Factoring integers The difficulty of factoring is presumably related to the irregularity of the pattern of divisors shown on page 909 . One approach to factoring a number n is just to try dividing it by each of the numbers up to √ n . … Typical running times for FactorInteger[n] in Mathematica 4 are shown below for the first 1000 numbers with each of 15 through 30 digits.

Somewhat related to the curves shown here is the function MoebiusMu[n] , equal to 0 if n has a repeated prime factor and otherwise (-1)^Length[FactorInteger[n]] .

Indeed, essentially the only problem on which cryptography systems have so far successfully been based is factoring of integers (see below ). … Significantly less work has been done on the problem of finding initial conditions for rule 30 than on the problem of factoring integers. But the greater simplicity of rule 30 might make one already have almost as much confidence in the difficulty of solving this problem as of factoring integers.

But if the multiplication factor at each step is 3, rather than 2, then the pattern obtained is quite different, as the second picture below shows. … Patterns produced by starting with the number 1, and then successively multiplying by a factor of 2, and a factor of 3. … Note that in these pictures the complete numbers obtained at each step correspond respectively to the successive integer powers of 2 and of 3.

This is nonzero when all prime factors of n of the form 4k + 3 appear with even exponents. … In 1973 it was proved that any even number can be written as the sum of a prime and a number that has at most two prime factors, not necessarily distinct. … Hardy and John Littlewood in 1922 to be proportional to 2n Apply[Times, Map[(# - 1)/(# - 2)&, Map[First, Rest[FactorInteger[n]]]]]/Log[n] 2 It was proved in 1937 by Ivan Vinogradov that any large odd integer can be expressed as a sum of three primes.

The total number of commutative groups with k elements is just Apply[Times, Map[PartitionsP[Last[#]] &, FactorInteger[k]]] (Relabelling of elements makes the number of possible operator forms up to k!

The number of cells that are not white on row t in this case is given by Apply[Times, 1 + IntegerDigits[t, k]] . (For non-prime k , the patterns are obtained by superimposing the patterns corresponding to the factors of k .) … Mod[Binomial[t, n], k] is given for prime k by With[{d = Ceiling[Log[k, Max[t, n] + 1]]}, Mod[Apply[Times, Apply[Binomial, Transpose[ {IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k]] The patterns obtained for any k are nested.

Fermat's Last Theorem That x n + y n  z n has no integer solutions for n > 2 was suggested by Pierre Fermat around 1665. … Then in 1847 Ernst Kummer used ideas of factoring with algebraic integers to prove it for all n < 37 .

Spin values can be thought of as specifying which irreducible representation of the group of symmetries of spacetime is needed to describe a particle after momentum has been factored out. … And this can be thought of as what allows half-integer spins, which must be described by spinors rather than vectors or tensors. … In the standard formalism of quantum field theory it can be shown that (above 2D) half-integer spins must always be associated with fermions (which for example satisfy the exclusion principle), and integer spins with bosons.

If k and n have no factors in common, there will be a t for which Mod[k t , n]  1 , so that the dot returns to position 1. … In general, the dot will visit position m = k^IntegerExponent[n, k] every MultiplicativeOrder[k, n/m] steps.