## Search found 450 matches

- Thu Jan 18, 2018 8:51 pm UTC
- Forum: Mathematics
- Topic: Lenstra's algorithm for divisors in residue classes
- Replies:
**2** - Views:
**1080**

### Re: Lenstra's algorithm for divisors in residue classes

I'm attempting to implement Lenstra's algorithm for finding divisors in residue classes as described as Algorithm 9.1.29 in Cohen's A Course in Computational Algebraic Number Theory (also available here in PDF form). [...] I tested this by evaluating list(moddiv(19, 101, 40320)), which should retur...

- Tue Oct 10, 2017 11:30 pm UTC
- Forum: Mathematics
- Topic: Estimating Max with Only Definite Integrals
- Replies:
**14** - Views:
**3636**

### Re: Estimating Max with Only Definite Integrals

The cost would be Q(n/p)k + S(p-1) if I choose to use p parallel streams. This is not ideal since it grows linearly with k and I have to make k large to ensure high probability of success. I don't see it pointed out explicitly, but this is not quite right; the growth of the minimal cost with k (cho...

- Tue Jul 25, 2017 10:33 pm UTC
- Forum: Mathematics
- Topic: Help with a recurrence relation, related to partitions, and related to random infinite permutations
- Replies:
**6** - Views:
**2515**

### Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

I would like to check to see that I understood correctly. The definition I gave of a(n) could be rephrased as a(n) = f(n) - (a*f)(n) (where * is involution) ...convolution, not involution; otherwise yes... and then A(n) = ∑ n a(n) x n is therefore = ∑ n ( f(n) - (a*f)(n) ) x n , and so A(n) = ∑ n (...

- Thu Jul 20, 2017 4:18 pm UTC
- Forum: Mathematics
- Topic: Help with a recurrence relation, related to partitions, and related to random infinite permutations
- Replies:
**6** - Views:
**2515**

### Re: Help with a recurrence relation, related to partitions, and related to random infinite permutations

I am looking at defining a function a(n) in terms of another function f(n), with a(n) defined as: a(n) = f(n) - ∑ i=1 n-1 ( f(i)*a(n-i) ) I have noticed that for some functions f, the sum of a(n) over positive integers n goes to 1. I have proved this for f(n)=1/(n+1) , as well as for f(n) = c , whe...

- Fri Mar 31, 2017 9:33 pm UTC
- Forum: Mathematics
- Topic: Smallest sum of digits of a multiple of n
- Replies:
**2** - Views:
**1853**

### Re: Smallest sum of digits of a multiple of n

Here are a couple of hints, which I think lead to a proof that min S(n) is unbounded: A number with digit sum d can be written 10 a(1) + ··· + 10 a(d) . So the set of all numbers with digit sum d, modulo n, is (almost; see caveat below) the "sum set" d*T = T + T + ··· + T (...

- Fri Dec 23, 2016 2:57 am UTC
- Forum: Mathematics
- Topic: expected "lifespan" of a random process
- Replies:
**4** - Views:
**1777**

### Re: expected "lifespan" of a random process

In your first equation, when you write T(n) = 1 + sum_{m=1}^{kn} B(kn,m) p^m T(m) . do you mean T(n) = 1 + sum_{m=1}^{kn} C(kn,m) (1-p)^(kn-m) p^m T(m) with C(kn,m) denoting kn choose m? I'm a bit confused by the B you use. Yes to both; I forgot the (1-p)^(kn-m) factor and wrote B instead of C (thi...

- Thu Dec 22, 2016 11:54 pm UTC
- Forum: Mathematics
- Topic: expected "lifespan" of a random process
- Replies:
**4** - Views:
**1777**

### Re: expected "lifespan" of a random process

Here's an alternate approach. (I don't know if it easily gives a closed form.) Let T(n) be the expected lifetime of the process, starting from x_0=n (you want T(1)). A single step follows the binomial distribution Binomial(kn,p), and T(0)=0, so T(n) = 1 + sum_{m=1}^{kn} B(kn,m) p^m T(m) . This is a ...

- Thu Dec 22, 2016 11:49 pm UTC
- Forum: Mathematics
- Topic: Probability distribution on the power set of natural numbers?
- Replies:
**12** - Views:
**2404**

### Re: Probability distribution on the power set of natural numbers?

Well, the infinite subsets with finite complements correspond precisely to these ambiguous cases with two representations. These are exactly the real numbers with terminating binary representations, and these are enumerable, so they have measure zero in [0,1]. That seems to be enough; have I missed ...

- Wed Aug 31, 2016 5:11 pm UTC
- Forum: Mathematics
- Topic: Torsion subgroups for elliptic curves over Q
- Replies:
**3** - Views:
**2086**

### Re: Torsion subgroups for elliptic curves over Q

Computing 12P directly is quite inefficient when P isn't a torsion point: for non-torsion points, the denominators of nP are about twice the size (in terms of bit length) of the denominators of (n-1)P, which slows down the computation dramatically. So it's much more efficient for non-torsion points...

- Tue Aug 30, 2016 6:14 pm UTC
- Forum: Mathematics
- Topic: Torsion subgroups for elliptic curves over Q
- Replies:
**3** - Views:
**2086**

### Re: Torsion subgroups for elliptic curves over Q

One thing that occurs to me is that for sufficiently large b-y 2 , rather than factoring b-y 2 and using the rational-root theorem, it's faster to estimate the real zeroes of the cubic x 3 +ax+(b-y 2 ) (e.g., using the closed-form solution to the cubic) and then check nearby integers. Your torsion-p...

- Thu Apr 21, 2016 5:29 pm UTC
- Forum: Mathematics
- Topic: Pi from the Menger Sponge
- Replies:
**9** - Views:
**3901**

### Re: Pi from the Menger Sponge

In all dimensions the identity is a form of the Wallis product. Basically all you have to do is count the factors in the numerator and denominator of the infinite product and shuffle the factors into the Wallis-product form, making sure that you keep the product convergent. Let's start by looking at...

- Fri May 29, 2015 7:40 pm UTC
- Forum: Logic Puzzles
- Topic: Are they in the same sequence?
- Replies:
**2** - Views:
**1858**

### Re: Are they in the same sequence?

Partial solution: The expression |G(n+1) 2 -G(n+1)G(n)-G(n) 2 | is invariant for any generalized double-ended Fibonacci sequence (Cassini's identity). So |d 2 -dc-c 2 |=|b 2 -ba-a 2 | if (a,b) and (c,d) come from the same sequence. But the ...

- Fri May 08, 2015 7:37 pm UTC
- Forum: Science
- Topic: Contamination of insulin pump cartridges
- Replies:
**23** - Views:
**4181**

### Re: Contamination of insulin pump cartridges

It seems like you could eliminate the contamination problems if you allow a little waste (but less than the 10% you're avoiding by using the last 1mL), by filling from the new vial first. This would mean you'd have to estimate the amount left in the old one so that you know how far to fill it, thoug...

- Fri Mar 13, 2015 4:55 am UTC
- Forum: Science
- Topic: Criticality of Thermodynamic Systems
- Replies:
**2** - Views:
**1829**

### Re: Criticality of Thermodynamic Systems

Rather than type up a big wall of text which may all be obvious to you, let me start with what may be a very simple question. The terminology of phase transitions and critical behavior is generalized from thermodynamics. Are you familiar with P-T phase diagrams? There's one as the first diagram (&qu...

- Sat Nov 15, 2014 9:34 pm UTC
- Forum: Mathematics
- Topic: Help me with this equations please!
- Replies:
**13** - Views:
**4248**

### Re: Help me with this equations please!

I don't see how you can determine for which values of r and s you get integer values for a and b. One way to parametrize the integer solutions is to convert the equation to Pell-like form, R 2 - n S 2 = (2nb-1) 2 - n (2a-n) 2 = 1 - n 3 = -8242407 . Given a solution (R 0 ,S 0 ) in in...

- Fri Oct 24, 2014 5:12 am UTC
- Forum: Mathematics
- Topic: How many ways can you prove x + 1/x >= 2?
- Replies:
**23** - Views:
**13671**

### Re: How many ways can you prove x + 1/x >= 2?

Geometry! ineq.png Let x>1. Construct right triangle ABC, with hypotenuse x+1/x and altitude 1; so ABC has area (x+1/x)/2. Now ADC and CDB are similar right triangles, so we can construct CEG congruent to CDB as shown, extending EG to complete unit square CDFE. The area of CDFE is 1, and the area of...

- Thu Oct 16, 2014 7:40 am UTC
- Forum: Mathematics
- Topic: Mildly interesting number theory question
- Replies:
**6** - Views:
**2542**

### Re: Mildly interesting number theory question

Here's a different argument: OVERVIEW: Let m>n. Tabulate the mn numbers from 1 to mn, in m rows of n numbers; for m=13 and n=10 it looks like this: coins-10-13.png Here I've partitioned the last row and column off separately. The black numbers are those not in the set ("unattainable&quo...

- Sun Aug 17, 2014 9:33 pm UTC
- Forum: Mathematics
- Topic: A nonlinear second-order ODE
- Replies:
**10** - Views:
**3479**

### Re: A nonlinear second-order ODE

This isn't a complete solution, but it's an approach to understanding the asymptotic behavior of physical solutions: We're looking for solutions to h m' m = 2 r m' - r 2 m'' where h=(Gμ)/(RT) (G the universal gravitational constant, R the ideal gas constant, T...

- Sun Aug 10, 2014 8:11 pm UTC
- Forum: Mathematics
- Topic: A nonlinear second-order ODE
- Replies:
**10** - Views:
**3479**

### Re: A nonlinear second-order ODE

It is possible I made a mistake deriving the equation though. Your derivation does have a mistake, which you can see by the fact that the constant-pressure configuration m(r)=ar 3 is not a solution when G=0: your derivation has PA constant instead of just P. The problem is in your force-balance equ...

- Thu Feb 06, 2014 5:59 am UTC
- Forum: Mathematics
- Topic: almost homework, a system in 3 unknowns
- Replies:
**11** - Views:
**2643**

### Re: almost homework, a system in 3 unknowns

alessandro95, are you familiar with Cardano's & Vieta's methods for solving cubics? For this cubic there's a more elegant proof that there's only one real solution. Here's a question. For f continuous and differentiable on R, if f has n zeroes then what is the minimum number of zeroes f' ca...

- Thu Jan 23, 2014 10:34 pm UTC
- Forum: Coding
- Topic: True normal distribution RNG?
- Replies:
**6** - Views:
**3836**

### Re: True normal distribution RNG?

What's your motivation here: what are the limitations of any of the standard algorithms that you're trying to fix? Anywhere beyond about 10 sigma the Gaussian tails are so small that they will probably be dominated in any physical process by other error sources. Far out on the Gaussian tails the pro...

- Thu Dec 19, 2013 5:07 am UTC
- Forum: Coding
- Topic: [done] Translating Mathematica to Python
- Replies:
**7** - Views:
**4519**

### Re: Translating Mathematica to Python

I think your line

should be

Code: Select all

` if a*x == r+y and a >= minden*x:`

should be

Code: Select all

` if a*x == r+y and a >= minden:`

- Thu Dec 19, 2013 3:41 am UTC
- Forum: Coding
- Topic: [done] Translating Mathematica to Python
- Replies:
**7** - Views:
**4519**

### Re: Translating Mathematica to Python

I'll eventually submit this to [url=sympy.org]SymPy[/url], so I'm using their built-in divisors method ( from sympy import divisors ). Hmm; I'd expect that to be fairly efficient. How long does divisors(1368857880324) take? When I run EgyptShort[31/311, 4] in Mathematica it only takes 0.25 seconds,...

- Thu Dec 19, 2013 2:37 am UTC
- Forum: Coding
- Topic: [done] Translating Mathematica to Python
- Replies:
**7** - Views:
**4519**

### Re: Translating Mathematica to Python

Have you profiled your code to find out where it's spending all its time? My guess, just because it's the only nontrivial function in the Mathematica code, is that you have an inefficient implementation of Divisors[y^2]. For your benchmark EgyptShort[31/311,4] , y gets as large as 1169982, which mea...

- Thu Nov 28, 2013 10:20 pm UTC
- Forum: Mathematics
- Topic: Different Numbers of Coins, Different Totals
- Replies:
**3** - Views:
**2113**

### Re: Different Numbers of Coins, Different Totals

Here's a brute-force O(n! 2 ) way to find the constraints. Compute all n!(n!-1)/2 "difference constraints" d ij =a(P i -P j ) , where the P i are distinct permutation matrices. A set v of coins has all of these values distinct iff all d ij v T !=0. Note that any permutation of the elements...

- Tue Nov 26, 2013 3:26 am UTC
- Forum: Mathematics
- Topic: Basic geometry: equilateral triangles
- Replies:
**7** - Views:
**1845**

### Re: Basic geometry: equilateral triangles

If you really want "pure Euclidean geometry" you can refer to Elements . That figures like jaap 's are correct is basically the content of Proposition I.32 (which does rely on the parallel postulate). That takes you most of the way there; you might want I.8 to argue that the six angles are...

- Sat Nov 23, 2013 5:47 pm UTC
- Forum: Mathematics
- Topic: What do I Google for this sort of "distribution"/"problem"
- Replies:
**7** - Views:
**2926**

### Re: What do I Google for this sort of "distribution"/"proble

The rest of the post, not-so-much. I'm having trouble wrapping my head around 0.3+0.7x^5 representing a state worth 2 points and a probability of 0.2 of getting those points. I'll have to play around with small sample data sets and see if I can get results that make sense. But yeah, N^2 where N is ...

- Sat Nov 16, 2013 4:54 am UTC
- Forum: Mathematics
- Topic: Cantor set problem from Pugh
- Replies:
**8** - Views:
**2263**

### Re: Cantor set problem from Pugh

This still leaves open whether there is any Cantor set on the circle whose chords form a convex set... Yes, this seems like a more interesting question to me. For Cantor sets where the interval (1/N,1-1/N) is removed, the triangular opening in the middle disappears for N < ~2.9. A graph like the on...

- Thu Nov 14, 2013 6:57 pm UTC
- Forum: Mathematics
- Topic: What do I Google for this sort of "distribution"/"problem"
- Replies:
**7** - Views:
**2926**

### Re: What do I Google for this sort of "distribution"/"proble

In the easy case, you're looking for the distribution of a sum of independent random variables (in this case, each of your 51 random variables is Bernoulli, and I'm assuming you already know the individual-state win probabilities). The density/mass function of a sum of random variables is the convol...

- Wed Nov 13, 2013 10:16 pm UTC
- Forum: Mathematics
- Topic: Cantor set problem from Pugh
- Replies:
**8** - Views:
**2263**

### Re: Cantor set problem from Pugh

I'm not sure I understand what "a Cantor set on the circle" is. If I wrap the usual 1/3 (or 1/N, with N>=3) Cantor set around the circle, identifying 0 and 1 with the same point on the circle, then it's easy to see that there's a triangular gap near the middle which cannot be filled by any...

- Wed Oct 16, 2013 1:31 am UTC
- Forum: Mathematics
- Topic: Excel Probability Question
- Replies:
**2** - Views:
**1535**

### Re: Excel Probability Question

First, the easy part: the algorithms. The naive algorithm to find the probability of exactly N successes, given your M trials, is to sum up the probabilities for all of the (M choose N) combinations of N successes and M-N failures. This is obviously not much fun for N bigger than about 2. A better w...

- Sat Oct 12, 2013 4:33 pm UTC
- Forum: Mathematics
- Topic: Can x+3 and x^2+3 both be perfect cubes?
- Replies:
**14** - Views:
**4321**

### Re: Can x+3 and x^2+3 both be perfect cubes?

Actually, I can do one better: For every prime p>3, at least one of -3, -2, 24 is a quadratic residue mod p. Proof: Assume that none of -3, -2, 24 are quadratic residues mod p, then -3, -2 are non-residues. Therefore 6 is a quadratic residue (the product of two non- quadratic residues is a resi...

- Sat Oct 12, 2013 6:13 am UTC
- Forum: Mathematics
- Topic: Can x+3 and x^2+3 both be perfect cubes?
- Replies:
**14** - Views:
**4321**

### Re: Can x+3 and x^2+3 both be perfect cubes?

One way we could possibly solve the problem of whether x 2 +3 is a cube (call it y 3 ) is to try modular arithmetic. x 2 =0,1,4(mod 8), so x 3 +3=3,4,7(mod 8). Therefore, since no cube is congruent to 4(mod 8), x is even, and y=3(mod 4). If you try the same trick modulo 7, you get that x=2,5(mod 7)...

- Sun Sep 08, 2013 7:03 am UTC
- Forum: Science
- Topic: Equation for field of a circular cross-section solenoid?
- Replies:
**7** - Views:
**2658**

### Re: Equation for field of a circular cross-section solenoid?

I am looking for an equation for the magnetic field in space around a solenoid of circular cross-section, i.e. a torus. All refrences I can find are either cylindrical solenoids or toroidal with the loops around the minor axis instead of major axis. \vec{B}(x,y,z) = ??? Even in the case of ...

- Fri Jul 12, 2013 4:49 am UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1190: "Time"
- Replies:
**105915** - Views:
**35570322**

### Re: 1190: "Time"

Valarya wrote:I believe ChronosDragon originally said Squaron for "S," which made me giggle. Squaron it shall be.

Nay! Squaron does not use the Elf-runes. S is for Squaruman, I guess.

- Sat Jun 29, 2013 5:24 pm UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1190: "Time"
- Replies:
**105915** - Views:
**35570322**

### Re: 1190: "Time"

Here's a Stellarium picture of the date (13291/04/14) I proposed above:[...] If this is what we're talking about I have some sad news... http://kieryn.com/xkcd-time/img/13291.png I suspect different versions give different results. This is from the win 64bit version. Essentially, I think at that fa...

- Sat Jun 29, 2013 5:21 am UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1190: "Time"
- Replies:
**105915** - Views:
**35570322**

### Re: 1190: "Time"

I think that's Jupiter; its position is very close to what Stellarium predicts for 13291/04/14. Darn, was about to say the same thing! Definitely Jupiter, and the date is around the 14th or 15th of April in 13291 ... So if this is 13291 (at something like 40°N latitude), then according to Stellariu...

- Sat Jun 29, 2013 4:22 am UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1190: "Time"
- Replies:
**105915** - Views:
**35570322**

### Re: 1190: "Time"

I think that's Jupiter; its position is very close to what Stellarium predicts for 13291/04/14.

- Sat Jun 29, 2013 2:14 am UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1190: "Time"
- Replies:
**105915** - Views:
**35570322**

### Re: 1190: "Time"

What we need to do is cycle through the millenia looking at Sagittarius until the celestial equator aligns with the straight line coming from the upper left corner. Then cycle through the months until the sun is in Lybra We need jupiter or Mars to complete the match (I'm on my phone right now so I ...

- Sat Jun 29, 2013 1:40 am UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1190: "Time"
- Replies:
**105915** - Views:
**35570322**

### Re: 1190: "Time"

What we need to do is cycle through the millenia looking at Sagittarius until the celestial equator aligns with the straight line coming from the upper left corner. Then cycle through the months until the sun is in Lybra We need jupiter or Mars to complete the match (I'm on my phone right now so I ...