Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

June 24

A big number

Hi, I have defined a big number N like this:

Define $f_{1}(x)=x^{x}\,$

Define $f_{i}(x)=f_{i-1}^{x}(x),\ i>1\,$

Define $N=f_{f_{10}(10)}(10)\,$

The notation $f^{n}(x)\,$ means the n-fold iteration of $f\,$. For example, $f^{3}(x)=f(f(f(x)))\,$.

My number N seems beyond incomprehensible, but how much bigger could we get with a definition of comparable length? Obviously we could tinker a bit, like changing "10" to "99", or writing $f_{1}(x)=x^{x^{x}}\,$, or whatever, but can we make a quantum leap to a whole new domain of incomparable vastness? 86.176.208.236 (talk) 02:46, 24 June 2011 (UTC)

Well, this kind of question is a bit boring to those of us who have been around for awhile, I'm afraid. You could make it more interesting by asking, for a given formal language such as the language of Principia Mathematica, what is the largest number that can be specified by an expression of length N? Looie496 (talk) 02:56, 24 June 2011 (UTC)

Very sorry to have bored you. You may find learning the difference between "a while" and "awhile" more interesting. 86.176.211.230 (talk) 13:25, 24 June 2011 (UTC)

Well, I wouldn't call it a quantum leap. It's quite well know. There are different kinds of infinity. For example, there are infinitly many integers and there are infinitely many real numbers. But some how the real numbers are more infinite than the integers; for example we think of integers as dots on a line while the real numbers are the whole line itself. A mathematician called Georg Cantor did a lot of work on this in the late 1800's and early 1900's. You should look at our articles on cardinals and ordinals. These guys are really crazy, but they're really cool too. I can't remember which one, I think it's an ordinal, but it's a fixed point of exponentiation; so if you take it to it's own power then you get it back again, i.e. x^x = x (and it's not one!) Take a look and see what you make of it. Feel free to pop back and ask some questions if you get stuck. — Fly by Night (talk) 03:29, 24 June 2011 (UTC)

What you've defined is basically the Ackermann function.--Antendren (talk) 04:08, 24 June 2011 (UTC)

"Incomprehensible" is a subjective and time-dependent concept. There is no such thing as a big number - every number is small because most numbers are bigger. Bo Jacoby (talk) 12:37, 24 June 2011 (UTC).

Take a look at Robert Munafo's large number pages for examples of definitions of large numbers. —Bkell (talk) 13:35, 24 June 2011 (UTC)

I like this number. Count Iblis (talk) 15:06, 24 June 2011 (UTC)

You may also be interested in the busy beaver function, which grows "faster asymptotically than does any computable function." SemanticMantis (talk) 13:42, 28 June 2011 (UTC)

Short form of the axiom of dependent choice

Resolved

I recently got the idea to convert the axiom of dependent choice to primitive symbols. I used Metamath to help me do this. I used the formulation of DC given on Wikipedia's page. When I was done, my formula had 559 quantifiers. Now, note this page. There is a formulation of full AC with only 5 quantifiers! Even if I converted my formula to prenex normal form, and was able to squash all quantifiers quantifying identical variables together (which the prenex normal form article makes it clear it is not), I still would have 18 quantifiers, and a formula approximately 100 times longer than the one given at the external link. Is there a known "short form" of dependent choice, like the one given at the external link for the full axiom of choice? If not, do you have any tips for creating a shorter formula (because I really can't believe mine is the shortest possible; I have the rest of ZF I can create equivalences over, and most of the equivalences I used in creating my formula in primitives were purely logical)? Thank you! JamesMazur22 (talk) 21:04, 24 June 2011 (UTC)

Just an unrelated question: since you seem to know a lot of converting everyday math into primitives, do you know if there's a primitive formula for the generalized associative law? The one that says the order of operation (e.g. in a group) doesn't matter if it's associative. Money is tight (talk) 03:06, 25 June 2011 (UTC)

$\forall x\forall y\forall z(x+y)+z=x+(y+z)$, $\forall x\forall y\forall z(x*y)*z=x*(y*z)$. Are those what you're looking for? Or do you mean in ZFC primitives? JamesMazur22 (talk) 13:18, 25 June 2011 (UTC)

I think Money is tight is asking about the generalization of that law to arbitrary-length expressions (dunno whether he's asking for ZFC primitives). So it seems you would first need to have an encoding of arbitrary-length expressions, and then state that any such expression with the same sequence of terms has a value independent of the parentheses in the expression. --COVIZAPIBETEFOKY (talk) 15:08, 25 June 2011 (UTC)

Yes COVIZAPIBETEFOKY is right I'm asking for the generalized associative law in ZFC primitives, and the functions symbols + or * are obviously not allowed. Can it even be expressed? I know that in the language of group theory the generalized associative law is really a metatheorem, I wonder if it can be converted into one formula in ZFC. Money is tight (talk) 02:35, 26 June 2011 (UTC)

That is a very long and difficult problem, albeit it is a possible one (create a sequence of sets, each set containing one set for each possible arrangement of parentheses for that many terms being added or multiplied, etc.). I could help you with it, but it might take me a while. In the meantime, is there anyone who can help me with my question? It is likely already published somewhere in the literature! JamesMazur22 (talk) 21:05, 26 June 2011 (UTC)

I didn't find a short form, but it turns out I really don't need it. And if I do, I will derive it myself. As for Money is tight's question, I think that answer is best continued on their talk page. I am capable of answering it myself, given some time. JamesMazur22 (talk) 15:21, 2 July 2011 (UTC)

Sum

Is there a closed form expression for $\sum _{k=1}^{n}{\frac {a^{k}}{k}}$ or for $\sum _{k=1}^{\infty }{\frac {a^{k}}{k}}$? Widener (talk) 22:48, 24 June 2011 (UTC)

From

$\log(1+x)=\sum _{k=1}^{\infty }(-1)^{k+1}{\frac {x^{k}}{k}}$

It follows that:

$-\log(1-x)=\sum _{k=1}^{\infty }{\frac {x^{k}}{k}}$

Count Iblis (talk) 23:04, 24 June 2011 (UTC)

First we have:

${\begin{aligned}{\frac {d}{da}}\sum _{k=1}^{n}{\frac {a^{k}}{k}}&=\sum _{k=1}^{n}{\frac {d}{da}}\,{\frac {a^{k}}{k}}=\sum _{k=1}^{n}a^{k-1}={\begin{cases}{\dfrac {1}{1-a}}&{\text{if }}n=\infty ,\\[15pt]{\dfrac {1-a^{n}}{1-a}}&{\text{if }}n<\infty .\end{cases}}\end{aligned}}$

Then look for antiderivatives. It's easier in the infinite case; you get a logarithm. In the infinite case it converges of −1 < a < 1, and uniform convergence of power series is needed to justify interchanging the d/da with the sum. Michael Hardy (talk) 00:29, 25 June 2011 (UTC)

I think it converges when a = −1 as well. Widener (talk) 04:06, 25 June 2011 (UTC)

Mathematica gives a closed form in terms of the Lerch transcendent,

$\sum _{k=1}^{n}{\frac {a^{k}}{k}}=-a^{n+1}\Phi (a,1,n+1)-\log(1-a)$

Also in terms of a hypergeometric function:

$\sum _{k=1}^{n}{\frac {a^{k}}{k}}=-{\frac {a^{n+1}{}_{2}F_{1}(1,n+1;n+2;a)}{n+1}}-\log(1-a)$

-- Meni Rosenfeld (talk) 14:31, 26 June 2011 (UTC)

June 26

Problem with Finite Integration

Problem with Finite Integration

My question is regarded as below:

http://farm4.static.flickr.com/3281/5872497175_ed916dd63a.jpg

Pls help. I'm desperate in need of a solution.Torment273 (talk) 17:32, 26 June 2011 (UTC)

Partial integration Integration by parts. Write the thing as $\int f(x)\sin x\,dx+\int f^{\prime \prime }(x)\sin x\,dx$. In the first term, set $u=f(x)$ and $v^{\prime }=\sin x$, in the second term, set $u^{\prime }=f^{\prime \prime }(x)$ and $v=\sin x$. You should end up with boundary terms only, from which you can read off $f(0)$. --Wrongfilter (talk) 19:07, 26 June 2011 (UTC)

That link doesn't go where you intend, I believe. Grandiose (me, talk, contribs) 19:09, 26 June 2011 (UTC)

Sorry, got fooled by a false friend. --Wrongfilter (talk) 19:12, 26 June 2011 (UTC)

June 27

Demographics and population statistics

There are many inconsistencies in the population statistics of the US. For example under the subject "United States" the leading urban centers use only the Untied States Office of Management and Budget's MSA statistics. Which are not footnoted as such. The stats are correct but there are two kinds of statistical areas (MSA and CSA) that the USOMB uses for information and should be clarified. Now if you look under the subject "Western United States" the city populations figures are different. For example the San Francisco area, as a USOMB MSA, does not rank in the top 10 cities of the United States but as a CSA it is 7.5 million. The "Western United States" uses the CSA statistics, which is fine, but should be noted or clarified to the reader. Furthermore in the "Western United States" subject, if you continue on down the list of cities to the Santa Rosa - Petaluma MSA, that is actually part of the San Francisco CSA. So that is doubling up on the numbers. Los Angeles is also incorrect on the "Western United States" page. If one is using the CSA then L.A.'s population should be about 18,000,000. These are huge discrepancies and may lead to incorrect facts being used. The CSA's and MSA's need to be clearly defined in these subject areas.

Aloha! — Preceding unsigned comment added by 72.130.193.92 (talk) 18:45, 27 June 2011 (UTC)

This page is for questions about Mathematics. Also, this is Wikipedia, the free encyclopedia that anyone can edit, WP:SOFIXIT. -- kainaw™ 18:48, 27 June 2011 (UTC)

You can also put those comments on the talk page(s) for those articles. StuRat (talk) 18:50, 27 June 2011 (UTC)

June 28

quick math question

Hi, I'm in the middle of doing a math problem and I was wondering if it would be okay to take the equation (x^2-9)^2-100x^2 and square root it all into x^2-10x-9? Thanks — Preceding unsigned comment added by 174.5.131.59 (talk) 01:32, 28 June 2011 (UTC)

If you want to solve (x² –9)² – 100x² = 0 then you can rewrite it as (x² –9)² = 100x². Both sides are greater than, or equal to, zero; that means we can take the square root without worrying about complex numbers. Taking the square root gives x² – 9 = ±10x. So you missed the ±. You should be able to solve from here. Remember that, counted with multiplicities, you should get four solutions for x. Solve x² – 9 = –10x for x (giving two solutions for x), and then solve x² – 9 = 10x for x (giving another two solutions for x).— Fly by Night (talk) 01:41, 28 June 2011 (UTC)

ohh that makes sense. Instead I fooled around with difference of squares and got (x^2-10x-9)(x^2+10x-9) but that looks like the same answer I got. Sorry for sounding dumb, but why does the square root need ± again? — Preceding unsigned comment added by 174.5.131.59 (talk) 02:10, 28 June 2011 (UTC)

If you multiply five by five you get 25. If you multiply minus five by minus five you again get 25. Symbolically, 5 × 5 = 25 and (–5) × (–5) = 25. That means that the answer to x² = 25 is either plus five or minus five, i.e. x = ±5. The difference of squares method is equally valid. Nice work. — Fly by Night (talk) 02:27, 28 June 2011 (UTC)

thanks that makes sense! — Preceding unsigned comment added by 174.5.131.59 (talk) 03:08, 28 June 2011 (UTC)

Widely accepted measure/metric of order

Is there a widely accepted measure or metric of order in a set? For example, 3127312631233128312 has a frequently recurring sequence 312, so there is a clear order throughout most of the data. However, 123456 has no order because each item occurs once. If that doesn't explain what I mean by "order", please ask for clarification. My idea is to use file compression which encodes frequent sequences of items in a series with a single code. Sets with high order will compress much further than sequences with no order. However, this is a short section in a mathematics paper, so I am hesitant to use something too computerish. -- kainaw™ 15:50, 28 June 2011 (UTC)

Not a direct answer, but I don't see the compression working very well, unless you have longer repeated sequences than 3 digits and more total digits. That's because the overhead involved in defining the repeating pattern(s) and assigning each a code (which you must assure doesn't exist in the rest of the digits) might actually make such a compression method increase the size. Then there's the question, with disk space so cheap these days, of whether the CPU time required to compress and decompress, and the additional complexity created, would be worth such a small space savings. StuRat (talk) 16:02, 28 June 2011 (UTC)

The sequences being used in this paper have around 200 million events. So, the overhead will be dwarfed by the size of the data sequence. I'm merely writing a section that is supposed to prove that the data sequences do have order. Given one event in the sequence, there is a probability that another specific event will show up later. An example in another section of the paper is: "Given that book 4 of the Harry Potter series is in a sequence of books purchased by a user of Amazon, there is a high probability that book 5 will occur later." -- kainaw™ 16:14, 28 June 2011 (UTC)

What you're talking about sounds like Entropy (information theory). I don't know much about information theory, but the compression you're talking about is maybe a Dictionary coder. Rckrone (talk) 16:18, 28 June 2011 (UTC)

I know Shannon entropy very well. I can't believe that I didn't make the correlation. I will define their term "order" as an absence of entropy and then I'm set. Thanks. -- kainaw™ 16:22, 28 June 2011 (UTC)

Entropy is a property of a random process, not of a specific sequence. Maybe what you're looking for is Kolmogorov complexity. -- Meni Rosenfeld (talk) 18:28, 28 June 2011 (UTC)

Entropy can be associated with a specific sequence, but it's not a property of the sequence alone. It's a property of how much information the sequence contains that an opponent does not have. So if you have say 1000000 bits of disk-time-access behavior that's fairly but not completely predictable, so that it contains 150 bits of entropy, you can use that together with a hash function to get a 128-bit key with confidence that the method of generation gives an opponent no advantage over trying all keys. However, if half the collection of access times were to be made public somehow, then you would only have 75 bits of entropy available (under the simplest assumptions), even though the collection itself has not changed. --Trovatore (talk) 00:06, 30 June 2011 (UTC)

Thanks. I vaguely remember that from undergrad networking algorithms class. I'm surprised it doesn't show up more in algorithms. Seeing as I'm already basing my little section on works by Levenshtein and Minkowski, why not toss in another Russian! -- kainaw™ 18:52, 28 June 2011 (UTC)

If anyone is interested, studying Kologorov complexity turns up that the standard practice is to perform sequence compression by replacing subsequences and then measuring the change in sequence length. The greater the change, the less entropy the sequence has. -- kainaw™ 00:13, 29 June 2011 (UTC)

Take your sequence and compress it with gzip or bzip2. Then take a random sequence of A, C, G, T (or whatever your alphabet is) of the same length as your original, and compress that. If your sequence compresses shorter than the random sequence, then it has structure. HTH, Robinh (talk) 20:02, 29 June 2011 (UTC)

June 29

I don't believe in mathematics.

I think mathematics ceases to be true when you stop believing in it. Therefore, by any reasonable definition of truth (such as the correspondence definition), mathematics is false. Mathematics in fact, need not correspond to anything in the real world. We do not even have a guarantee that the real world exhibits logic, or only seems to. Moreover, mathematics is a simplification and abstraction: therefore, its only purpose can be decoration and embellishment: to take the bare reality, and distill a structure from it that is nowhere there. There is no circle: yet what is a circle, mathematically a locus of points? What are points. Mathematicians fantasies, full of sound and fury, and corresponding to nothing. I do not believe in mathematics. --188.29.241.38 (talk) 22:42, 29 June 2011 (UTC)

Not believing in mathematics means, at best, that you are uninformed. Of course you can believe that it does not reflect reality. That position is at least consistent. But then you must explain The Unreasonable Effectiveness of Mathematics in the Natural Sciences. --Stephan Schulz (talk) 22:51, 29 June 2011 (UTC)

Check, and mate. Where's the "like" button? — Fly by Night (talk) 23:02, 29 June 2011 (UTC)

At worst, is it a Tea thing? --188.28.169.51 (talk) 23:28, 29 June 2011 (UTC)

This page is supposed to be for asking questions. Michael Hardy (talk) 23:03, 29 June 2011 (UTC)

Okay. How can I succinctly disprove the proposition assumed by The Unreasonable Effectiveness of Mathematics in the Natural Sciences, viz. that mathematics is effective in the natural sciences? --188.28.169.51 (talk) 23:30, 29 June 2011 (UTC)

I guess the most appropriate and effective tool for that would be mathematics. Dmcq (talk) 23:58, 29 June 2011 (UTC)

• I think it's best that we leave this section as it stands, per don't feed the trolls. The maths reference desk is not a forum. It's a place where people ask mathematical questions, and where the reference desk regulars help to answer those questions with the use of Wikipedia articles. Coming to the maths reference desk and saying that you don't believe in mathematics is, besides deranged, an obvious attempt to insight conflict. You have come to the wrong place for that. — Fly by Night (talk) 00:02, 30 June 2011 (UTC)

Here is a list of irrefutable proofs that mathematics is false.

HTH. --COVIZAPIBETEFOKY (talk) 01:00, 30 June 2011 (UTC)

The poster has a point. If you e.g. believe in the Axiom of Choice, the continuum etc. etc. then you must live with the Banach–Tarski paradox Count Iblis (talk) 01:45, 30 June 2011 (UTC)

Once you strip away the "I don't believe" rhetoric, there are several interlinked questions here. Let's try to untangle them:

1. Is mathematics a practically effective model that allows us to predict and manipulate the physical world around us ? Undoubtedly, yes.
2. Is mathematics the most effective model of the physical world that we know of ? Again, yes.
3. Is mathematics the only way of interacting with the physical world ? No. Trial and error works well enough in some areas (home cooking, for example), but it is very inefficient.
4. Does every part of mathematics have some connection to the real world ? Not necessarily, although it is surprisingly difficult to name an area of mathematics that has absoutely no real world applications.
5. Can mathematics be effectively applied to all areas of human experience ? No (or, at least, not yet). Interactions between people, from individual relationships to global politics, do not seem to be very amenable to mathematical analysis.
6. Could there be a more effective way of modelling and manipulating the physical world than mathematics ? We don't know. Magic and crystal balls don't seem to work over here, but maybe in a galaxy far, far away things might be different.
7. Is the effectiveness of mathematics "unreasonable" ? That's a matter of opinion, and it depends on how you define "reasonable".
8. Does the effectiveness of mathematics reveal something deep about the physical world ? Or is it just an artefact of how we perceive the physical world ? Now that's a good question ... Gandalf61 (talk) 09:56, 30 June 2011 (UTC)

Regarding #5 - while mathematics is far from "solving" human interactions, game theory can give a lot of mileage in analyzing both interpersonal and international relationships. -- Meni Rosenfeld (talk) 11:08, 30 June 2011 (UTC)

1 + 1 = 2 is true at least until Hell freezes over - after that all bets are off. Whether you believe in it or not makes absolutely no difference to the truth of it. A statement that you don't believe in mathematics is effectively the same as declaring yourself an idiot and/or insane. Roger (talk) 11:08, 30 June 2011 (UTC)

Maybe Hell has frozen over. Has anyone been there lately? Can mathematics even prove it exists, or doesn't exist? -- Jack of Oz ^{[your turn]} 11:51, 30 June 2011 (UTC)

The existence of hell is a trivial corollary of a theorem by Euler. -- Meni Rosenfeld (talk) 13:06, 30 June 2011 (UTC)

Judging by his link, Roger (Dodger) apparently thinks the Universe is Hell. Now that's depressing. --Trovatore (talk) 17:21, 30 June 2011 (UTC)

Actually, what he wrote only presupposes that Hell is in the universe, and will be the last part of the universe to freeze over. Michael Hardy (talk) 05:48, 1 July 2011 (UTC)

That sort of takes me back. In high school I took a literature course in which we had a certain series of short stories in film form shown on television in the classroom. In one of the stories (which may have been by Updike but then again maybe not) a vicar is discoursing on Purgatory, and remarking that, for some subtle theological reason I probably didn't understand then and don't remember now, beings in Purgatory were physical beings, and therefore purgatory, unlike Heaven or Hell, had to be a place. But where? he wanted to know.

So if the vicar was right, the heat death of the Universe might freeze over Purgatory, but not Hell.

Does this story ring a bell with anyone? I'd kind of like to know the name of it. --Trovatore (talk) 06:51, 1 July 2011 (UTC)

Missing from this list: "Is mathematics 'true'"? The answer is "no". --188.29.128.61 (talk) 22:40, 30 June 2011 (UTC)

Saying that mathematics is "true" is like saying that soccer is true. Mathematics is an activity, not a set of truths. Looie496 (talk) 16:02, 30 June 2011 (UTC)

Mathematics is an activity aimed at discovering truths. (I was going to say "unlike soccer", but then again, who knows?) --Trovatore (talk) 17:23, 30 June 2011 (UTC)

Well, soccer certainly has no other discernible purpose, function or meaning. (God knows, I've looked long and hard, but not a sausage.) We already know, courtesy of Bill Shankly, that soccer is far more important than life or death. So, it's looking very much like its sole raison d'etre is to discover truths. Who knew? -- Jack of Oz ^{[your turn]} 08:59, 1 July 2011 (UTC)

OP, I have to agree with you there. I used to "believe" in math, but now I realized what you say is indeed true: it's just a fanatasy. All I do is write down meaningless symbols that's meant to represent some other worldly mental image. None of this stuff exist, it's all just random talk. Money is tight (talk) 15:05, 1 July 2011 (UTC)

Thank you (OP here), your response is helpful. However, it does not answer any of my questions (perhaps because I didn't raise any?) 87.194.221.239 (talk) 16:23, 1 July 2011 (UTC)

June 30

Factorising an integer into 2 integers

What is a good way to factorise a 16-bit integer into 2 8-bit integers so that the product is as close to the 16-bit integer as possible? I'm trying to emulate a high resolution PWM signal with 2 8-bit PWMs, one running at 1/256 of the clock speed of the other, so that PWM-A would have completed a whole period in the time PWM-B completes 1 count. Therefore the overall duty cycle = A*B/65536, except with reduced precision as the duty cycle increases (which is not a problem). I need to set A*B to any arbitrary amount but I'm not sure how to factorise it, since most factorisation articles focus on prime factorisation with 2+ factors. I thought of an algorithm that shifts the 16-bit integer to the right until it fits in an 8-bit integer and store that into A, while shifting B leftwards by the same amount, effectively reducing the problem to X ~= A * 2^N. This is done on a small microcontroller so things like floating point numbers need to be avoided. Is there a better but still reasonably simple algorithm that can achieve better precision? Thanks. --antilived^{T | C | G} 03:05, 30 June 2011 (UTC)

Is there some reason why you can't just use the first 8 bits as one number and the last 8 bits as the other ? StuRat (talk) 03:11, 30 June 2011 (UTC)

No, because of numbers like 0x0100 would actually give me 0 duty cycle. Basically I'm masking PWM-A with PWM-B - so for example if PWM-B is set to 1 then at the output there would only be a pulse generated by PWM-A 1/256 of the time - or PWM-A AND PWM-B. To achieve what's equivalent to 0x0100 on a 16-bit PWM timer I need to put in either 0x01FF or 0x027F or one of the other combinations, except finding the best combination has been quite challenging. --antilived^{T | C | G} 08:49, 30 June 2011 (UTC)

Gosh that takes me back. I once produced a watchdog timer using two spare serial comms timers linked up like that. I'm afraid I can't think of any better way rather than starting with zero and 255 as the two values and incrementing one number till the product is too high then decreasing the other till it is too low and repeating till one goes out of range, all the while comparing the product with the target and recoding when you get a result that is closer. Actually you can just start with the negative of the number and add or subtract one of the numbers as the other is incremented or decremented, that way you never do an actual multiplication and the difference is there all the time so you can find the closest negative and positive ones. You're talking about at most 256 increments or decrements so it might be okay for you. The general problem is equivalent to factorizing a large number and that is a difficult problem used to making secure cyphers. Dmcq (talk) 07:18, 30 June 2011 (UTC)

Atmel AVRs actually have a hardware multiplication instruction for 8-bit numbers so multiplications don't have that much of a penalty. I'll try out your way and see how well that works - although now to think of it perhaps it's not as big a problem as I thought it would be. I'm doing brightness control on LEDs and accuracy is only important at low intensities. Since the error is proportional to 2^N but the brightness function is also ~2^N the perceived error would be constant and not really a problem at all. I need to experiment with the circuit more; thanks for your help though. --antilived^{T | C | G} 08:49, 30 June 2011 (UTC)

Do you mean you are using a 16-bit integer to specify the brightness of each LED ? That seems excessive. An 8-bit integer should do, giving you 256 brightness possibilities. Since it's easier to perceive the difference between an LED at 0/255 and 1/255 brightness than between 254/255 and 255/255, you may want to use a (nonlinear) look-up table to convert each integer into the true brightness (which might be the 16-bit integer value). Or, you could apply a formula, like 16BIT = 8BIT + round((1.04425788)^(8BIT + 1)) - 1. This formula would give a mapping like so:

  8BIT       16BIT
-------   ----------- 
  0/255       0/65535
  1/255       1/65535
  2/255       2/65535
  3/255       3/65535
  4/255       4/65535
  5/255       5/65535
  6/255       6/65535
  7/255       7/65535
  8/255       8/65535
  9/255      10/65535
        .
        .
        .
253/255   60117/65535
254/255   62767/65535
255/255   65535/65535

StuRat (talk) 14:34, 30 June 2011 (UTC)

If I understand this correctly, you have a 16 bit integer from 0000000000000000 to 1111111111111111 and you want two 8 bit integers that, when multiplied together, are very close to the original number. So, take the floor of the square root of the 16 bit integer. The result will be an integer from 00000000 to 11111111 (because 11111111² is 1111111111111111). If you like, you can add 1 to one of the two square root factors if the actual result has a fraction that is rather high. Then, you won't lose as much accuracy as using the floor. -- kainaw™ 13:09, 30 June 2011 (UTC)

(edit conflict)Here's an idea: Let N be the number to factor. Let a be the smallest integer greater than √N (use binary search to find this to avoid floating point operations). Let b be the closest integer to N-a². Then N is approximately equal to (a+b)(a-b). E.g. given N=14850, a=122, b=6, 128×116=14848, off by 2.--RDBury (talk) 13:18, 30 June 2011 (UTC)

But 14850 = 99 x 150, so 128 x 116 = 14848 is close, but not "as close as possible". Gandalf61 (talk) 14:12, 30 June 2011 (UTC)

It's still a pretty good algorithm for the job. I like it, just wish I had someplace to use it :) Dmcq (talk) 14:52, 30 June 2011 (UTC)

I think there are some typos in the above. Let me try without typos. Let

${\begin{aligned}a&=\left\lceil {\sqrt {N}}\right\rceil \\b&=\left\lfloor {\sqrt {a^{2}-N}}+1/2\right\rfloor \,.\end{aligned}}$

Then $(a+b)(a-b)$ will be pretty good. —Quantling (talk | contribs) 17:48, 30 June 2011 (UTC)

Gerrymandering Mathematics

I was wondering about this example given in the article on gerrymandering. The article states:

In (a), creating 3 mixed-type districts yields a 3–0 win to Plum — a disproportional result considering the state-wide 9:6 Plum majority.

In (b), Orange wins the urban district while Plum wins the rural districts — the 2-1 result reflects the state-wide vote ratio.

In (c), gerrymandering techniques ensure a 2-1 win to the state-wide minority Orange party.

I would like to know: is this the simplest (fewest voters) and most disproportionate example mathematically possible? Thank you in advance for any help. --CGPGrey (talk) 15:45, 30 June 2011 (UTC)

My reply, reposted from the Humanities desk:

Heck, I'm no mathematician, but it's an easy one if you come from the country that once had Rotten boroughs, like I do. It's definitely not the most extreme example. The most extreme example would be to create 7 districts, one of which contains all the plums and the other six holding one orange each, resulting in a 6-1 victory for orange. Even better would be if you could disbar the plum voters from enfranchisement, gaining a 6-0 whitewash for the party that should have lost. --Dweller (talk) 15:59, 30 June 2011 (UTC)

I think there might be an implied stipulation that the districts be equal in population. In that case I think this is indeed the most distorted possibility. If there are three districts, you have to give one of them to plum, so 2-1 is the best you can do. If there are five districts with three voters each, the best you can do is to make three districts with two orange voters and one plum, leaving two all-plum districts. Overall that comes out 3-2, or again an advantage of 1 for orange, but proportionally less (so plum can win a vote if one orange councilman out of three defects, instead of one out of two). --Trovatore (talk) 21:21, 30 June 2011 (UTC)

How about 3 districts with 3 voting blocks in each:

OOP
PPP
POO

You can get 2/3 P districts by dividing them into 3 columns, or 2/3 O districts by dividing them into 3 rows. StuRat (talk) 16:05, 30 June 2011 (UTC)

Assuming all districts have equal numbers of voters and that every voter belongs to one of two parties, the most extreme possible result is for a party with N% of voters to control 2N% of districts. Thus a party with 10% of voters can control 20% of districts; a party with 50% of voters can control all districts. If there are no constraints on district sizes or on the number of parties, there are no constraints on how extreme the outcome can be. Looie496 (talk) 16:14, 30 June 2011 (UTC)

Number of orientations of face centers for Rubik's Cube

Resolved

I believe the Wikipedia article on the Rubik's Cube to be wrong about how many ways there are to orient the six face centers of a Rubik's Cube (when they have markings on them that indicate their orientation); can you help prove me right or wrong? With disassembly of the cube permitted, each of the six centers can be oriented in one of four ways, so there are $4^{6}$ possible orientations; no argument there. But how many orientations can be achieved when disassembly is prohibited? The article says that half of the $4^{6}$ orientations can be achieved, but I believe it to be one quarter of them. In particular, I believe that if the cube has all side and corner pieces arranged and oriented correctly and has five of its six centers oriented correctly then it will necessarily have the sixth center oriented correctly. However, the article indicates, in effect, that it is possible that the sixth center will be 180° out of proper orientation. If the article and its source are indeed correct, what is the "algorithm" that rotates a center by 180° without changing the arrangement or orientation of any other piece? (This paragraph substantially duplicates a discussion I have also tried to start on the Rubik's Cube talk page. If you reply in one of these locations, please consider dropping a quick link at the other.) Thanks! —Quantling (talk | contribs) 17:33, 30 June 2011 (UTC)

Never mind. I figured out the algorithm. —Quantling (talk | contribs) 17:59, 30 June 2011 (UTC)

July 1

Fourier series

I was reading about Fourier series and have a doubt concerning it. The book I am reading from does not seem to help. As I understand, $\{e_{0}={\frac {1}{\sqrt {2}}},e_{1}=sin(x),e_{2}=cos(x),e_{3}=sin(2x),e_{4}=cos(2x)\cdots \}$ is a basis for the inner product space of piecewise continuous functions in $[-\pi ,\pi ]$ with inner product $\langle f,g\rangle ={\frac {1}{\pi }}\int _{-\pi }^{\pi }f{\bar {g}}$. Hence any function in this space may be represented by $f=\sum _{k=0}^{\infty }\langle f,e_{k}\rangle e_{k}$. My question is what happens at points of discontinuity x. As f is identical with the series $f=\sum _{k=0}^{\infty }\langle f,e_{k}\rangle e_{k}$ (which by the way is unclear to me as to why it coverges) shouldn't f(x) be identical with the series at x, i.e. $f(x)=\sum _{k=0}^{\infty }\langle f,e_{k}\rangle e_{k}(x)$. But Dirichlet's theorem (stated without proof in my book) says that at points of discontinuity, the series $\sum _{k=0}^{\infty }\langle f,e_{k}\rangle e_{k}(x)$ converges to ${\frac {f(x-)+f(x+)}{2}}$ and not to f(x). Why is this so? Thanks-Shahab (talk) 01:41, 1 July 2011 (UTC)

It comes from the proof of Foruier Series itself. Where do the coefficients come from? Why do they involve integrals? If a function satisfies Dirichlet's conditions then its Fourier series converges to

${\frac {1}{2}}\left(\left[\lim _{x\to a^{-}}f(x)\right]+\left[\lim _{x\to a^{+}}f(x)\right]\right)$

for all $a\in [-L,L].$ If the function is continuous then both summands are equal and it converges to the value. If it's not continuous at a then it converges to the average. I suppose that that's the fundamental thing to realise; that it always converges to the average of the two limits. — Fly by Night (talk) 02:34, 1 July 2011 (UTC)

I think you misunderstood my post. Forget about Dirichlet's conditions for the moment. I claim that the coefficients are $\langle f,e_{k}\rangle$ from linear algebra and that they involve integrals by definition of my inner product. Now I hope my question is clear.

Also, what kind of convergence do we generally have in case of infinite bases?-Shahab (talk) 02:59, 1 July 2011 (UTC)

I don't think I misunderstood. I just try to suggest a way to answer the question that you asked. Why should they involve integrals? Why should the series have any meaning whatsoever? Does your book have a section that shows where the Fourier series comes from, and why it is defined the way it is? 03:17, 1 July 2011 (UTC)

That inner product can't distinguish between two functions that only differ at a single point (or more generally at any set of measure zero). If f₁ and f₂ are two square-integrable functions that are equal except at the point x₀, then $\langle f_{1},g\rangle =\langle f_{2},g\rangle$ for any square-integrable function g. It should be clear that f₁ and f₂ have the same Fourier series. We can't reasonably expect that Fourier series to converge at x₀ to both f₁(x₀) and to f₂(x₀). To maybe rephrase the point made by Fly by Night, the Fourier series can't "see" what happens at a specific point, only what happens in the vicinity of a point, because that's how integrals work and the inner product is defined in terms of integration. Rckrone (talk) 03:15, 1 July 2011 (UTC)

I think that the space of piecewise continuous functions in [ − π,π] is not inner-product, since it has nonzero elements with a norm of 0. So $f=\sum _{k=0}^{\infty }\langle f,e_{k}\rangle e_{k}$ needn't apply. -- Meni Rosenfeld (talk) 05:03, 1 July 2011 (UTC)

Also piecewise continuous functions in [−π, π] are not necessarily square-integrable, so the Fourier coefficients may not even be well-defined. Rckrone (talk) 05:41, 1 July 2011 (UTC)

Hmm...I think the book is wrong for it explicitly states that the space of piecewise continuous functions is inner product.-Shahab (talk) 12:24, 1 July 2011 (UTC)

You have weak convergence. Count Iblis (talk) 15:12, 1 July 2011 (UTC)

Actually, it's strong convergence in the Hilbert space L². A relevant article is convergence of Fourier series. 15:30, 1 July 2011 (UTC)

Yes, of course. My brain malfunctioned :) .Count Iblis (talk) 16:14, 1 July 2011 (UTC)