# Tag Info

26

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

14

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

11

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

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

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

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

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], ...

7

initial side note: As J.M. correctly points out this is not an efficient implementation and serves only to illustrate behavior similar to the Python function all. If you are looking for a similar definition to the Python code you give, then you could use this: isPrime[n_] := And @@ Table[Mod[n, i] != 0, {i, Range[2, n - 1]}] This creates a table of ...

7

Try to use lowercase names at least for the initial letter of your functions. My timings are different than yours. Probably your computer is much faster than mine. In your code pro is calculated in 144 seconds and GCD[func[160001],pro] needs another 34 seconds so a total of 178 seconds. Of course pro is calculated only once but the same happens in the ...

6

Here's a fancy memoized solution: Clear[primePowerCount, primePowerCountcache, iPrimePowerCount] iPrimePowerCount[n1_, n2_] := Count[Range[n1, n2], _?PrimePowerQ] primePowerCountcache = {1}; primePowerCount[1] = 0; primePowerCount[n_?Positive] := Module[{n0, res}, n0 = First@Nearest[primePowerCount`cache, n]; If[n0 < n, res = ...

6

I had a clever idea for how to do this using LatticeReduce[], but I decided to code up the Smith-Cornacchia algorithm first to bench mark against, and it was effectively instant for inputs in your range. Here is a sloppy implementation. In particular, I am embarrassed by applying Divisors[] to something which is computed as a product. However, the result is ...

6

Given a large n, to find k largest primes below n (as well as above) the best approach uses NextPrime (it has been added to Mathematica 6) : NextPrime[n] gives the next prime above n. NextPrime[n,k] gives the k-th prime above n. If k is negative it gives k-th largest prime below n. k need not be a single number but it may be a list of ...

6

Addendum If you just want the greatest 10 primes less than M, you can start from Prime[PrimePi[M]-9]. By doing so, you gain a speed increase of 2 orders of magnitude when M = 100000. M = 100000; m = PrimePi[M] AbsoluteTiming[Table[Prime[k], {k, m - 9, m}]] 9592 {0.000171, {99877, 99881, 99901, 99907, 99923, 99929, 99961, 99971, 99989, 99991}} Now ...

6

What I really wanted to post was an alternative way of generating the grid. In my humble opinion, it's better to do it with Table without Partition as it looks better in code. But since Animate has already been dealt with, three times over, let me also use an alternative method for that: color[n_] := Style[n, Which[100 Clock[1, 10] < n, Black, PrimeQ@n, ...

5

Starting with a styling funtion: st = Style[#, If[PrimeQ@#, {Bold, Blue}, Gray]] &; For fast operations and small tables you can use MapAt: Animate[ MapAt[st, Range@100, List /@ Range@i] ~Partition~ 10 // Grid, {i, 0, 100, 1} ] In version 9 you can use Span for better performance: Animate[ MapAt[st, Range@100, ;; i] ~Partition~ 10 // Grid, {i, ...

5

!! WARNING !! Given the above circumstances the answer below is completely wrong and should not be replicated rather than used for guideline. The problem lies in the fact that Assumptions DON'T affect summation indices hence they are disregarded in the code below. You can evaluate the series using the following snippet: Sum[1/(k n (k + n)^2), {k, 1, ∞}, ...

5

I can't complete with Artes's mathematical knowledge and approach, but simply as a point of reference, for formulating a brute-force approach it will be more memory efficient to use Sum, though it will still be very slow for large input. Sum[Boole @ PrimePowerQ @ i, {i, 5*^6}] // Timing MaxMemoryUsed[] {46.535, 348940} 15083688

3

Not sure if this is what you are after but maybe if its not it will help you clarify the question: long = RandomInteger[10^30]; base = 2^32; repr = IntegerDigits[long, base]; Total@MapIndexed[ #1 base^(First@#2 - 1) &, Reverse@ repr] == long StringJoin[ MapIndexed[ If[First@#2 > 1, "+", ""] <> ToString[#1 ] <> Table[ ...

3

Late again, but ... In addition toPrimePowerQ, the built-inMangoldtLambda[n]also works as in n - Count[MangoldtLambda[Range[n]], 0] where n is the upper limit. However, these functions are both too slow. The answer by @Artes usesPrimePieffectively for much faster results. A cool method given by Riemann himself is to usePrimePion fractional powers of the ...

3

You can useFindInstanceto specify the number of solutions desired as in FindInstance[{p == x^2 + y^2, x>0, y>0, x>y}, {x, y}, Integers, 1] for large random primep. However, the following Cornacchia algorithm is faster thanFindInstanceorSolve, on my machine, and perhaps is open to optimization... Cornacchia[p_] := Block[{r, a, s}, r = ...

3

I post here my latest and final code. I am adding an additional post to expose a clear code. At first we define func and we put in prp list the candidate exponents. prp = {}; func[q_] := 77^q + 2; Do[If[TimeConstrained[PrimeQ[func[i]], 1, True], AppendTo[prp, i]], {i, 160000, 161000}] Then the following function returns the exponents from the list ...

3

Just a small change and you get a free speedup : rather than looping over 10000 and then calculating Prime[p] each time, do a Prime[Range[10000]] once and for all. SeedRandom[6]; random = RandomPrime[10^1000]; initialList = Table[k random + 1, {k, 1, 2000}]; list = initialList; counter = 2000; {elapsedOP, resultOP} = Do[Do[If[Divisible[n, Prime[p]], list = ...

3

Quote from MSieve (one of the more popular factorization programs): On a fast modern CPU, a 110-digit QS factorization takes nearly 120 hours for Msieve. A 100-digit one should be significantly less than that. So, no, it does not take 100 years. The trouble you are having fitting your data is not that there are too few points, but the distribution of ...

3

Here is a way to get close. ParallelTable[ Sum[1/(k n (k + n)^2), {k, N@Prime[Range[i]]}, {n, N@Prime[Range[i]]}], {i, 10, 2000, 10}] This gives the following output: {0.0445365, 0.0448078, 0.0448455, 0.0448556, 0.0448597, 0.0448617, <<188>>, 0.0448652, 0.0448652, 0.0448652, 0.0448652, 0.0448652, 0.0448652} Which can be plotted ...

3

The most straightforward way of evaluating your sum in Mathematica is as follows: Sum[1/(Prime[k] Prime[n] (Prime[k] + Prime[n])^2), {k, 1, Infinity}, {n, 1, Infinity}] See for instance the last example on the how-to EvaluateInfiniteSumsAndProducts. This returns unevaluated however, so it seems that if there is a closed form for this series then ...

2

Here is a fast implementation which translated from Matlab's primes function, And is slightly faster than that one。 primes[n_ /; n >= 2 && IntegerQ[n]] := Module[{p = Range[1, n, 2]}, p〚1〛 = 2; Do[ If[ p〚(k + 1)/2〛 != 0, p〚(k^2 + 1)/2 ;; ;; k〛 = 0], {k, 3, n^.5, 2}]; SparseArray[p]["NonzeroValues"] ]; primes[10^7] // Length // ...

2

Well, this is not really an answer to your question, just something that came to mind when reading it & I thought I'd share. Note that I am sure that there are better ways to implement it (there must be some nice code to create the spiral... but I wanted to implement what I had in mind). depending on what the aim is (large number, animation, ...

2

I don't exactly know what I'm doing, but...here is an outline using Smith's method to recast a number as a sum of squares. the overall approach is this. (1) Factor into ordinary primes. (2) For each ordinary prime p, factor over Z[sqrt(-3)]. (3) Now replace sqrt(-3) with 2ω+1. Clearly (1) and (3) are straightforward in Mathematica. For (2) one can do as ...

1

For fun, here's an approach that uses ReplaceList: With[{n = 50}, Union @@ ReplaceList[ Array[Prime, n], {pre___, y_, rest___} :> y {pre, y}]] (* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, \ 55, 57, 58, 65, 69, 77, 85, 87, 91, 95, 115, 119, 121, 133, 143, 145, \ 161, 169, 187, 203, 209, 221, 247, 253, 289, 299, 319, 323, ...

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