Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

12

A concrete example would be helpful. Here is a simple way to count solutions, illustrated by example. Generate random set of smallish positive integers. nlist = Union[RandomInteger[{8, 80}, 12]] (* Out= {9, 16, 19, 35, 41, 42, 58, 59, 68, 74, 78} *) Form a product of binomials. prod = Times @@ (1 + x^nlist) (* Out= (1 + x^9) (1 + x^16) (1 + ...

9

Here's a guess: The Diophantine problem $$x^2+y^2+x+y=a$$ is equivalent, via $u=2x+1,v=2y+1$ to finding the odd solutions to $$u^2+v^2=2+4a \,.$$ Whether Solve makes this transformation or not, solving the Pythagorean equation can be done from the prime factorization of $2+4a$. How long Solve takes thus might depend on how long it takes to factor $2+4a$. ...

6

For the first problem, if you have enough memory available you could just generate all subsets and count how many times they form a certain sum: aa = {7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; Rest@BinCounts[Total /@ Subsets[aa]] {1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8, 10, 10, 11, 12, 13, 14, 16, ...

5

Note that it's hard to know how 'efficient' you need without supplying specific examples. If you're only interested in a single instance, you can reduce this problem to the 0-1 knapsack problem (or equivalently 0-1 ILP) by calling KnapsackSolve. Unfortunately I don't see an immediate (built in) way to find more than one solution with this approach. (* ...

4

The approach suggested by yarchik can be accelerated by two orders of magnitude by performing the computations with machine precision numbers instead of exact numbers and then rounding, and by using ParallelDo: SetSharedVariable[s] s = {}; ParallelDo[If[IntegerQ[(1 + a*Round[Sqrt[1./(a*a) + 12. (a + 1)], 10^-10])/6], AppendTo[s, a]], {a, 1, 10^9}] // ...

3

You can replace Table with Do Do[If[IntegerQ[1/6 (1 + Sqrt[1 + 12 a^2 + 12 a^3])], Print[a]], {a, 1 + 10^(11), 10^4 + 10^(11)}] but it is still slow. Try to bring your diophantine equation to some known type.

3

To solve the full problem, I don't know how to coax Mathematica into running 100 nested Do's in a reasonable amount of time. Instead, I would use Mathematica to generate C-code that is then executed externally. In this way, the the full problem can be solved in about 40 seconds. Here's the Mathematica code that generates the C-code. Assume that we want $\... 3 All the$n_i$with$i>100$must be zero, so it's enough to look at$n_1\ldots n_{100}$. The below code will crash for this large system though. However, if you only look at$i\le i_{\text{max}}$(and you may make$i_{\text{max}}\$ as large as your computer allows, though probably not 100 as truly needed), then you could first generate the list of all ...

2

For the simultaneous equations case, you can again use SeriesCoefficient as in Daniel's answer to get the number of solutions. For instance: SeedRandom a = Range; b = RandomSample[1;;30, 10]; Using SeriesCoefficient: SeriesCoefficient[Times @@ (1 + x^a y^b), {x, 0, 12}, {y, 0, 37}] 2 Using Solve to confirm: Solve[ a.x == 12 && b.x =...

2

One approach is to name your variables as elements of an array (instead of having separate names). For example, allA defines 100 variables called a, a, etc. You can use these in Solve directly, and force them all to be positive integers: n = 100; allA = Array[a, n] Solve[{Sum[a[i], {i, 1, n}] == 100 && Sum[i a[i], {i, 1, n}] == 1000 &&...

1

I used FrobeniusSolve but in the most wasteful way imaginable. I solved these two equations separately and found the intersection of the solutions and counted how many there are as a function of U. The Log of this number is the entropy of the system. The physical model is a set of N identical marbles occupying an infinite staircase where ascending each step ...

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