Wikipedia:Reference desk/Archives/Mathematics/2011 August 31

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 31

When is xxxx0831 prime?

For which years, when a decimal number in the format of yyyymmdd, is the 31st August a prime number? example: is 20110831 a prime number? Ohanian (talk) 02:37, 31 August 2011 (UTC)

WolframAlpha will answer your second question: Is 20110831 a prime number? —Bkell (talk) 04:40, 31 August 2011 (UTC)

There are 1298 such years with 4 digits, computed and counted with this PARI/GP line:

c=0;for(x=1000,9999,if(isprime(x*10000+831),print1(x", ");c++));c

The years between 1900 and 2100: 1906, 1916, 1921, 1924, 1925, 1955, 1958, 1966, 1976, 1979, 1987, 1990, 2003, 2014, 2017, 2021, 2023, 2038, 2045, 2047, 2054, 2065, 2068, 2071, 2077, 2081, 2093, 2096, 2099. PrimeHunter (talk) 04:56, 31 August 2011 (UTC)

Dirichlet's theorem on arithmetic progressions implies that there are an infinite number of such primes.--RDBury (talk) 06:26, 31 August 2011 (UTC)

That is, assuming you allow more than 4 digits in the year.--RDBury (talk) 06:29, 31 August 2011 (UTC)

Speaking of large years, the largest possible number of prime days in a month is nine. It can only happen for days 1, 3, 7, 9, 13, 19, 21, 27, 31, so it requires a month with 31 days. The first occurrence is in May 20349980. The first day in the first occurrence for each possible month: 17573603340101, 71431649320301, 203499800501, 18759860550701, 15187449080801, 93726474391001, 294920291201. Guess the reason for my username. PrimeHunter (talk) 15:29, 31 August 2011 (UTC)

Solving a problem with constraints

Given $x_{1},...,x_{n}\in \mathbb {R^{+}}$ is there an algorithm for choosing $a_{1},...,a_{n}\in \mathbb {N} \cup \{0\}$ so as to maximize $\sum _{k=1}^{n}a_{k}x_{k}$ subject to the constraint that $\sum _{k=1}^{n}a_{k}x_{k}\leq N$ for some $N\in \mathbb {R^{+}}$ ? Widener (talk) 03:55, 31 August 2011 (UTC)

This is an integer linear programming problem, so those techniques could be applied. More specifically, this is a special case of the unbounded knapsack problem, where the weight and value of each item are equal. The classic way to solve knapsack problems is dynamic programming. See Knapsack problem#Unbounded knapsack problem for more details. —Bkell (talk) 04:29, 31 August 2011 (UTC)

I guess that the constraint is $\sum _{k=1}^{n}a_{k}\leq N$ for some $N\in \mathbb {N}$ ? Bo Jacoby (talk) 10:14, 31 August 2011 (UTC).

Not necessarily. An unbounded knapsack problem in which the weight of each item is equal to its value is still an interesting problem. It may still be NP-complete—offhand I don't see any reason that this restriction of the problem would make it easier. —Bkell (talk) 17:57, 31 August 2011 (UTC)

NP-completeness follows by reduction from the subset sum problem. 188.117.30.209 (talk) 19:01, 4 September 2011 (UTC)

How does that reduction work, exactly? I'm thinking about encoding an instance of the subset sum problem as an unbounded knapsack problem in which the weight and value of each item are equal, but I don't quite see how to do it. —Bkell (talk) 11:32, 5 September 2011 (UTC)

Sum of n-sums

Hi. I am trying to simplify the sequence defined by

$u_{n}=\sum _{k_{1}=1}^{n}k_{1}+\sum _{k_{1}=1}^{n}\sum _{k_{2}=1}^{k_{1}}k_{2}+\dots +\sum _{k_{1}=1}^{n}\sum _{k_{2}=1}^{k_{1}}\dots \sum _{k_{n}=1}^{k_{n-1}}k_{n}$

In other words, (sum of all numbers to n) plus (sum of sums up to n) plus ... plus (sum of sum of ... of sums [n times] up to n). If I've calculated the first few terms correctly, then according to OEIS the formula is probably ^{2n + 1}C_{n + 1} − (n + 1), but I'm out of my depth trying to establish this. Some help with simplifying the sum would be appreciated. Also, as a side interest, is there some notation to avoid the clumsy dots in the definition of u_n? i.e. some notation for repeated sigmas/pis/integrals? —Anonymous Dissident^Talk 12:31, 31 August 2011 (UTC)

Just to clarify, expanding out the first three values:

u1=1=1

u2=1+2+1+1+2=7

u3=1+2+3+1+1+2+1+2+3+1+1+1+2+1+1+2+1+2+3=31.

Is that correct?--RDBury (talk) 14:27, 31 August 2011 (UTC)

I'm sure there's an elegant combinatorial argument for this, but here's an algebraic one. Denote $a_{0,n}=n,\ a_{m,n}=\sum _{i=1}^{m}a_{m-1,i}$. Then $a_{1,n}=\sum _{k_{1}=1}^{n}k_{1}$, $a_{2,n}=\sum _{k_{1}=1}^{n}\sum _{k_{2}=1}^{k_{1}}k_{2}$ etc., so $u_{n}=\sum _{m=1}^{n}a_{m,n}$. Now, $a_{m,n}=a_{m,n-1}+a_{m-1,n}$ and from this it is easy to show, using induction and Pascal's rule, that $a_{m,n}={\binom {m+n}{m+1}}$. It's not hard now to show that $u_{n}={\binom {2n+1}{n+1}}-(n+1)$.

For notation, you can sum over sequences rather than over numbers. You can write

$\sum _{k_{1}=1}^{n}\sum _{k_{2}=1}^{k_{1}}\dots \sum _{k_{m}=1}^{k_{m-1}}k_{m}=\sum _{\begin{smallmatrix}K\in [n]^{m}\\\forall i,j(i\leq j\Rightarrow K_{i}\geq K_{j})\end{smallmatrix}}K_{m}$

where $[n]$ is a (not universally recognized) notation for $\{x\in \mathbb {N} |1\leq x\leq n\}$, $A^{m}$ is the set of sequences of length m with entries taken from A, and $\forall i,j(i\leq j\Rightarrow K_{i}\geq K_{j})$ says that the sequence is nonincreasing. Then

$u_{n}=\sum _{m=1}^{n}\sum _{\begin{smallmatrix}K\in [n]^{m}\\\forall i,j(i\leq j\Rightarrow K_{i}\geq K_{j})\end{smallmatrix}}K_{m}$

-- Meni Rosenfeld (talk) 14:46, 31 August 2011 (UTC)

Let

$v_{n,2}=\sum _{k_{1}=1}^{n}k_{1}$

$v_{n,3}=\sum _{k_{1}=1}^{n}\sum _{k_{2}=1}^{k_{1}}k_{2}$

etc. And extend this to

$v_{n,0}=1$

$v_{n,1}=n$

Then

$v_{n,i+1}=\sum _{k_{1}=1}^{n}v_{k_{1},i}$

$v_{n,i}=v_{n-1,i}+v_{n,i-1}$

From which, using induction, the v's are binomial coefficients

$v_{n,i}={\binom {n+i-1}{n-1}}$

So

$u_{n}=v_{n,2}+v_{n,3}+\dots +v_{n,n+1}=-(1+n)+v_{n,0}+v_{n,1}+\dots +v_{n,n+1}$

$={\binom {n-1}{n-1}}+{\binom {n}{n-1}}+\dots +{\binom {2n}{n+1}}={\binom {2n+1}{n+1}}$

which gives the expression you gave.--RDBury (talk) 14:57, 31 August 2011 (UTC)

(There was an edit conflict, my solution is probably equivalent to Meni's.)--RDBury (talk) 15:01, 31 August 2011 (UTC)

is it correct

-15=-15

9-24=25-40=>3^2-4*3=5^2-4*5

3^2-4*3+8^2=5^2-4*5+8^2

(3-8)^2=(5-8)^2

3-8=5-8

3=5 — Preceding unsigned comment added by 117.254.148.104 (talk) 12:39, 31 August 2011 (UTC)

Well obviously not, as 5 does not equal 3. Your error occurs in the implication in the second line. Once this is fixed, the same line of reasoning allows you to conclude that the square of -1 is equal to the square of 1 -- clearly, true. (Slightly edited the OP's formatting...) Icthyos (talk) 13:34, 31 August 2011 (UTC)

What you wanted to write is

-15=-15

9-24=25-40=>3^2-2*4*3=5^2-2*4*5

3^2-2*4*3+4^2=5^2-2*4*5+4^2

(3-4)^2=(5-4)^2

3-4=5-4

The last line basically says, "3-4 and 5-4 have the same square, so they must be equal". This makes about as much sense as "my brother and I have the same parents, so I am my brother." -- Meni Rosenfeld (talk) 15:06, 31 August 2011 (UTC)

A very common question I've seen on many exams... x²=1. What is x? Most people answer 1 and forget that it has two answers, 1 and -1. I've never understood why this question is deemed to be of much importance - so I tend to notice it a bit more than other questions, like the many variations of 3-4-5 triangles. -- kainaw™ 17:24, 31 August 2011 (UTC)

Difference quotient

Resolved

 – Ks0stm ^(T•C•G) 00:26, 1 September 2011 (UTC)

One last homework question (following WP:RD/M#Geometry functions) that has me stuck. "Evaluate the difference quotient for f(x)=2+x-3x²." The answer I got was x+3h, but I was unsure enough along the line that I have a gut feeling that's not right, but is it or not? If not, I can post my work I got there with. Thanks, Ks0stm ^(T•C•G) 23:17, 31 August 2011 (UTC)

Try again. Note that the difference quotient should be equal to $f'(x)$ after taking the limit as h approaches 0. Nm420 (talk) 23:38, 31 August 2011 (UTC)

(edit conflict) Your answer doesn't look right because the limit as h tends to zero of the difference quotient is equal to the derivative. The limit of x + 3h as h tends to zero is x, while dƒ / dx = 1 – 6x. If I'm right, then the difference quotient if given by [ƒ(x+h) – ƒ(x)] / h. Well

${\frac {1}{h}}\left(f(x+h)-f(x)\right)={\frac {1}{h}}\left([2+(x+h)-3(x+h)^{2}]-[2+x-3x^{2}]\right).$

If we expand this term by term and then cancel and simplify, we get

${\frac {1}{h}}\left(f(x+h)-f(x)\right)={\frac {1}{h}}\left(h(1-3h-6x)\right)=1-3h-6x\,.$

This answer looks better because the limit of 1 – 3h – 6x at h tends towards zero is 1 – 6x which is dƒ / dx. Always remember to check your answers if you can. — Fly by Night (talk) 23:41, 31 August 2011 (UTC)

I'm lost somewhere between those two steps...I go from your first one to (2+x+h+3x²-3xh-3h²-2+x-3x²)/h, and I think I make my error somewhere between those two. I just don't know what it is. Ks0stm ^(T•C•G) 23:54, 31 August 2011 (UTC)

I think you have some of your signs wrong. Try 2 + x + h - 3x^2 - 6xh - 3h^2 - 2 - x + 3x^2. Probably. --Tagishsimon (talk) 23:59, 31 August 2011 (UTC)

Got it! I did have signs wrong, but apparently I also messed up the FOIL on the (x+h)². I found that and corrected it and the signs and once I did that it all went fine. Thanks to everyone! Ks0stm ^(T•C•G) 00:26, 1 September 2011 (UTC)