(The probability for s randomly chosen integers to be relatively prime is 1/Zeta[s] .) … In general the density for an arrangement of white squares with offsets v is given in s dimensions by (no simple closed formula seems to exist except for the 1 × 1 case) Product[With[{p = Prime[n]}, 1 - Length[Union[Mod[v, p]]]/p s ], {n, ∞ }] White squares correspond to lattice points that are directly visible from the origin at the top left of the picture, so that lines to them do not pass through any other integer points. … Its computation is known in general to be equivalent in difficulty to factoring n (see page 1090 ).

It is known that any odd perfect number must be greater than 10 300 , must have a factor of at least 10 6 , and must be less than 4 4 s if it has only s prime factors. … Various generalizations of perfect numbers have been considered, requiring for example IntegerQ[DivisorSigma[1, n]/n] (pluperfect) or Abs[DivisorSigma[1, n] - 2n] < r (quasiperfect).

In the system x  Mod[2x, n] from page 257 , the repetition period MultiplicativeOrder[2, n] probably cannot always be computed in any polynomial of Log[n] steps, since otherwise FactorInteger[n] could also be computed in about this number of steps.

An alternative formulation is to ask whether for all n FixedPoint[(3#/2^IntegerExponent[#, 2] + 1)/2 &, n]  2 With the rule n  If[EvenQ[n], 5n/2, (n + 1)/2] used in the main text, the sequence produced repeats if n ever reaches 2, 4 or 40 (and possibly higher numbers). … And with this assumption, n should increase by a factor of 5/2 half the time, and decrease by a factor close to 1/2 the rest of the time—so that after t steps it should be multiplied by an overall factor of about ( √ 5 /2) t . … If one applies the same kind of argument to the standard 3n+1 problem, then one concludes that n should on average decrease by a factor of √ 3 /2 at each step, making it unsurprising that at least in most cases n eventually reaches the value 1.

The evolution of the arithmetic system is given by ASEvolveList[{n_, rules_}, init_, t_] := NestList[(Mod[#, n] /. rules)[#] &, init, t] Given a value m obtained in the evolution of the arithmetic system, the state of the register machine to which it corresponds is {Mod[m, p] + 1, Map[Last, FactorInteger[ Product[Prime[i], {i, nr}] Quotient[m, p]]] - 1} Note that it is possible to have each successive step involve only multiplication, with no addition, at the cost of using considerably larger numbers overall.

And indeed in 1994 Peter Shor found a way to do this so as to get quantum computers at least formally to factor integers of size n using resources only polynomial in n . … And depending on FactorInteger[m] the resulting amplitudes show fairly large differences which can then be detected in the probabilities for different outcomes of measurements. … (Factoring is not known to be NP-complete.)

Thus for example if x is an integer with n digits then evaluating Sin[x] or FractionalPart[x c] requires respectively finding π or c to n -digit precision. … The best-known algorithms for evaluating Zeta[1/2 +  x] (see page 918 ) to fixed precision take roughly √ x operations—or 2 n/2 operations if x is an n -digit integer. … Unlike for continuous mathematical functions, known algorithms for number theoretical functions such as FactorInteger[x] or MoebiusMu[x] typically seem to require a number of operations that grows faster with the number of digits n in x than any power of n (see page 1090 ).

History [of cryptography] Cryptography has been in use since antiquity, and has been a decisive factor in a remarkably large number of military and other campaigns. … Initially several different problems were considered, but after a while the only ones to survive were those such as the RSA system discussed below based essentially on the problem of factoring integers.

Writing a in terms of distinct factors as r s , {r + s, r - s}/2 gives a solution if it yields integers—which happens when Abs[a] > 4 and Mod[a, 4] ≠ 2 . • x 2  a y 2 + 1 (Pell equation). … For most values of a (including specifically a = 1 ) the continuous version of this equation defines a surface of genus 3, so there are at most a finite number of integer solutions. … As for the equations above, there are always at most a finite number of integer solutions. • x 3 + y 3  z 2 + a .

.) • Is there a solution of a certain size to an integer linear programming problem? … It is not known whether problems such as integer factoring or equivalence of networks under relabelling of nodes (graph isomorphism) are NP-complete.