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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < August 30 ! width="25%" align="center"|<< Jul | August | Sep >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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{+}}$ 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\le N$ for some $N\in {ℝ}^{\mathbb{+}}$ ? 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\le 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}=(\genfrac{}{}{0ex}{}{m+n}{m+1})$. It's not hard now to show that $u_n=(\genfrac{}{}{0ex}{}{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{array}{c}K\in [n{]}^m\\ \mathrm{\forall }i,j(i\le j\Rightarrow K_i\ge K_j)\end{array}}{K}_m$

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

$u_n=\sum _{m=1}^n\sum _{\begin{array}{c}K\in [n{]}^m\\ \mathrm{\forall }i,j(i\le j\Rightarrow K_i\ge K_j)\end{array}}{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}=(\genfrac{}{}{0ex}{}{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}$

$=(\genfrac{}{}{0ex}{}{n-1}{n-1})+(\genfrac{}{}{0ex}{}{n}{n-1})+\dots +(\genfrac{}{}{0ex}{}{2n}{n+1})=(\genfrac{}{}{0ex}{}{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

Template:Resolved One last homework question (following WP:RD/M#Geometry functions) that has me stuck. "Evaluate the difference quotient for Template:Math." The answer I got was Template:Math, 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^{\prime }(x)$ after taking the limit as h approaches 0. Nm420 (talk) 23:38, 31 August 2011 (UTC)

Template:Ec 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 Template:Nowrap as h tends to zero is x, while Template:Nowrap. If I'm right, then the difference quotient if given by Template:Nowrap. Well

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

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

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

This answer looks better because the limit of Template:Nowrap at h tends towards zero is Template:Nowrap which is Template:Nowrap. 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 Template:Math, 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 Template:Math. 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)