Tag Info

Hot answers tagged

30

If not assumed otherwise m and n can be whatever, so you can do e.g. this : Solve[ Prime[n] + Prime[m] == 100, {n, m}, Integers] {{n -> 2, m -> 25}, {n -> 5, m -> 24}, {n -> 7, m -> 23}, {n -> 10, m -> 20}, {n -> 13, m -> 17}, {n -> 15, m -> 16}, {n -> 16, m -> 15}, {n -> 17, m -> 13}, {n -> 20, m ...


21

Note: I am not particularly knowledgable in the field of this question, so what I write below may well be wrong. I don't know whether or not this should be considered a bug, but to my mind this is an instance of a clash of programming and mathematical functionality. To put it differently, predicates (functions ending with Q) seem to be a wrong match for ...


21

This answer should be read upside down, since the last edit has the fastest, neatest and shortest answer Module[{$guard = True}, happyQ[i_] /; $guard := Block[{$guard = False, appeared}, appeared[_] = False; happyQ[i] ] ] e : happyQ[_?appeared] := e = False; happyQ[1] = True; e : happyQ[i_] := e = (appeared[i] = True; ...


21

PrimeQ and FactorInteger use different algorithms. In general asking whether a number is prime is an easier problem than finding its factors. To quote the documentation, "PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test", while "FactorInteger switches ...


19

The built-in functionPrimeOmega gives you the number of prime factors and counts multiplicities. Therefore, this can easily be used to give you semi-primes as you have defined them: With[{r = Range[50]}, Pick[r, PrimeOmega[r], 2]]


18

It's due to an implementation-dependent issue. We should try to improve on it. Has not been much clamor to do so, therefore it has not been a high priority. --- edit --- I've had a look at the code. It is quite intentional that the largest is around what you state (I see the constant being set to $7.783516108362\times 10^{12}$). It has to do with this ...


17

Actually, I believe the issue reduced to that of implementing PrimePi[]. It is easy to implement Prime[] using PrimePi[] and FindRoot[] — in fact this is done on page 134 of Bressoud and Wagon, "A Course in Computational Number Theory". So all you need is to have a fast implementation of PrimePi[]. The first efficient way was found by Legendre in 1808. The ...


17

I want to answer the part of the question, "How could my son be expected to find a prime factor?" Well, this depends on what your son has been taught, of course. A first thing to notice is that, since 99! is divisible by every prime less than 99, 99! - 1 is not divisible by any of those primes; so 101 is the smallest prime which could be a factor of it. So ...


16

In general Mathematica cannot compute symbolically infinite sums over primes because of the lack of appropriate mathematical tools. However there are infinite products over primes which are basically well understood on the mathematical level. One famous example is the Euler formula for the Riemann zeta function, one of the most beautiful (and mysterious ...


16

I believe this is correct, and very fast: fn[x_Integer, n_Integer] := Complement[Range @ x, Join @@ Range[#, x, #]] & @ Prime @ Range @ n Test: fn[10000, 1223] {1, 9929, 9931, 9941, 9949, 9967, 9973} It seems I am a bit late to return to this problem and Simon Woods already provided a memory optimized approach. His sieve is comparatively ...


16

This is competitive with Mr Wizards code and seems faster in some cases: fn2[x_Integer, n_Integer] := Module[{y = Range @ x}, (y[[# ;; x ;; #]] = 0) & /@ Prime[Range @ Min[n, PrimePi @ x]]; SparseArray[y]["NonzeroValues"]] AbsoluteTiming[fn[10000, 1223];] (* {0.004000, Null} *) AbsoluteTiming[fn2[10000, 1223];] (* {0.010001, Null} *) ...


15

You could use FactorInteger to find out whether or not there are exactly two primes building up a number: SemiPrimeQ[n_Integer] := With[{factors = FactorInteger[n]}, Total[factors[[All, 2]]] == 2 ] The rest is easy: Select[Range[50], SemiPrimeQ] (* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49} *) And for those who like inline ...


12

Simple top-level solution Here is a simplistic completely top-level code: ClearAll[happyQ]; happyQ[n_] := Block[{appeared}, appeared[_] = False; Take[ NestWhileList[ Total[IntegerDigits[#]^2] &, n, (! appeared[#] && (appeared[#] = True)) & ], -2] == {1, 1}]; Clear[happyPrimeN]; ...


12

This probably counts as cheating, since it uses the fact that all unhappy numbers end up in a cycle including 4. But I like it for simplicity... happyQ[1]=True; happyQ[4]=False; happyQ[n_]:=happyQ[n]=happyQ[#.#&@IntegerDigits[n]] This works with Leonid's happyPrimeN function.


11

It has been explained in good detail why your inputs did not work the way you wanted them; however, there is still a way to get what you want: Resolve[Exists[n, Element[n, Primes] && Mod[n, 2] == 0]] True FindInstance[Element[n, Primes] && Mod[n, 2] == 0, n, Integers] {{n -> 2}} In general, use Element[n, Primes] whenever you need to ...


11

I prefer Bold and Larger in Style: Animate[ Grid[ Partition[ Table[ Style[i, Bold, Larger, If[i > j, Black, If[ PrimeQ @ i, Blue, Gray]]], {i, 100}], 10], Spacings -> {1, 1}], {j, 0, 100}, Paneled -> False] but if you like delete from ...


10

Clear[happyPrimeN]; happyPrimeN[2000] = 137653; happyPrimeN[2000] // AbsoluteTiming {0., 137653} But seriously, here's a memoised, recursive happyQ that can be used with Leonid's happyPrimeN Clear[sos, happyQ]; sos[k_Integer] := sos[k] = #.# &[IntegerDigits[k]]; happyQ[k_Integer] := happyQ[k] = happyQ[k, {}]; happyQ[1, history_List] := True; ...


10

A naive approach would be this: primePower[n_] := Count[ Range @ n, _?PrimePowerQ] This function works well however it might be very inefficient for large n. It takes a bit to evaluate e.g. primePower[10^6] 78734 which is only a little bigger than PrimePi[10^6] 78498 The latter is much more efficient since it uses advanced algorithms for ...


9

(nextPrime[#1] = #2) & @@@ {{-3, 2}, {-2, 2}, {-1, 2}, {0, 2}, {1, 2}, {2, 3}}; nextPrime[n_Integer?EvenQ] := nextPrime[n - 1]; nextPrime[n_Integer] /; PrimeQ[n + 2] := n + 2; nextPrime[n_Integer] := nextPrime[n + 2] nextPrime[n_ /; n \[Element] Reals] := nextPrime[Floor@n]


9

Here's my take: (* Brent's algorithm for cycle detection *) happyQ[start_Integer] := Module[{cyc, f, hare, pow, tortoise}, f = Total[IntegerDigits[#]^2] &; cyc = pow = 1; tortoise = start; hare = f[start]; While[tortoise =!= hare, If[pow == cyc, tortoise = hare; pow *= 2; cyc = 0;]; ...


9

Minimization can be expressed with plain NMinimize in a bit awkward manner: NextHighlyCompositeNumber[n_Integer?Positive, primes:{__Integer?PrimeQ}] := With[{parms = Unique[] & /@ primes}, With[{eqn = Inner[Power, primes, parms, Times]}, Floor@First@NMinimize[{eqn, eqn >= n && parms \[Element] Integers && And @@ ...


9

You can do : Reduce[Prime[n] + Prime[m] == 100, {n, m}, Integers]


8

Might be faster to do batches by checking for nontrivial gcds. Below I group 100 primes into each batch, take their products, and do a gcd computation until finding that there is a divisor. The example sieves a million primes. random = RandomPrime[10^1000]; list = Table[k random + 1, {k, 1, 2000}]; pprods = Apply[Times, Partition[Prime[Range[10^6]], 10^3], ...


8

Here is my method (not sure it counts): happyPrimeN = Import["http://oeis.org/A035497/b035497.txt", "table"][[#, 2]] & happyPrimeN[2000] // AbsoluteTiming Out[14]= {0.7490428, 137653}


8

Artes's answer is just fine. This variation works as follows. When you click on a number, the background of that number turns yellow and that of each of its divisors turns light blue. DynamicModule[{s = 101}, Grid[Partition[Dynamic@Button[Style[#, 16], (s = #), Background -> Which[ # == s, Yellow, Divisible[s, #], LightBlue, True, White], Appearance ...


8

By using a pregenerated list of prime numbers: lst = Prime[Range@PrimePi[25]]; Select[Union@Flatten[lst*# & /@ lst], # < 50 &] (* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49} *)


8

I cannot take credit for this, but here is a rather interesting and compact implementation that I found somewhere: F[n_] := {Re[#], Im[#]} & /@ Fold[Join[#1, Last[#1] + I^#2 Range[#2/2]] &, {0}, Range[n]] G[n_] := Table[#[[Prime[k]]], {k, 1, PrimePi[n^2/4 + 1]}] &[F[n]] ListPlot[G[500], AspectRatio -> Automatic] Whether that is faster than ...


8

In a nutshell, factoring integers is a harder problem than determining primality. This seeming asymmetry is exploited as a component in modern computer security systems (in the form of the RSA cryptosystem). Determining primality has long been known to be doable in polynomial time using a variety of probabilistic algorithms, many of which (as mentioned by ...


8

Times @@ Power @@@ {{2, 1}, {3, 2}, {43, 5}, {26684839, 1}}


8

As noted in the comments this behavior follows from the definition of FromDigits, though I only understood this myself within the last year or two when someone* used it to boost performance. Consider a symbolic example: sym = FromDigits[{a, b, c}] sym /. { a -> {a1, a2, a3, a4, a5}, b -> {b1, b2, b2, b4, b5}, c -> {c1, c2, c3, c4, ...



Only top voted, non community-wiki answers of a minimum length are eligible