Mathematics desk
< February 13	<< Jan \| February \| Mar >>	February 15 >

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.

February 14[edit]

Number naming system[edit]

Why is the system for naming large numbers built around 1000 rather than some other power of 10 (e.g. 10000)? --108.225.117.174 (talk) 01:04, 14 February 2012 (UTC)[reply]

Completely abritrary choice, I think. Ancient Egyptians had dedicated names for powers of 10 up to 1,000,000. Greeks had a system based on 10,000. East Asians use 10,000 as well: see Myriad#History and usage.--Itinerant1 (talk) 01:24, 14 February 2012 (UTC)[reply]

I suspect it's related to why we put commas (or decimals) every three digits. That is, you can remember only so many digits at a time, maybe around 3-4. So, dividing numbers up in groups of 3 or 4 makes sense. I occasionally need to copy a number without divisions every few digits (like with some web sites that want a credit card number but don't allow spaces) and find it quite irritating. StuRat (talk) 02:09, 14 February 2012 (UTC)[reply]

See Digit grouping. Note that "groups of three" is not a cultural universal, even today. Lakh describes how in India the least three significant digits of an integer are grouped, and subsequent digits are grouped in pairs. As StuRat suggests, their naming is reflected by this grouping. Powers of ten in Thai all have their own names, and are not grouped. Where you would call 2,345,678 "two million, three hundred forty-five thousand, six hundred seventy-eight", in Thai ๒๓๔๕๖๗๘ would be spoken as "song lan, sam saen, si muen, ha phan, hok roi, chet sip paet" -- literally "two million, three hundred-thousand, four ten-thousand, five thousand, six hundred, seventy-eight". -- 110.49.235.82 (talk) 06:38, 14 February 2012 (UTC) (I've used our article's Thai transliterations here. What little Thai I know I learned phonetically, and have come up with my own transliteration which often fails to precisely match what I see written.)[reply]

Apparently they do group the last two digits. Otherwise it would end "...seven tens and eight ones". StuRat (talk) 21:57, 14 February 2012 (UTC)[reply]

Only in the same sense as with English where, "Spelled-out two-word numbers from 21 to 99 are hyphenated (e.g. fifty-six)" (from WP:Numbers#Typography -- do we have a real article which gives a name to this practice?) and certain two digit numbers have their own special names ("eleven, twelve, ... nineteen" in English and "sip et, song sip et, ... kao sip et" (eleven, twenty-one, ... ninety-one, where "et" is used for one instead of the regular "nueng") in Thai). While we write and speak it this way, we don't usually think of this as a "group of two" in English, do we? Also note that the commas I put in the transliteration wouldn't be present in the actual Thai as they don't even put spaces between words. -- 203.82.91.156 (talk) 02:59, 15 February 2012 (UTC) (Previously posted as 110.49.235.82 -- Thailand yesterday, Malaysia today.)[reply]

Is there an accepted name for systems of naming numbers where powers of 1000 play an important role, say, rather than 10000? Also, the metric system seems awfully unfair on East Asians. 96.46.204.126 (talk) 00:18, 15 February 2012 (UTC)[reply]

I would say "chiliadic" and "myriadic", but that's just me. I believe that the Japanese have names for the two systems, though, but I don't remember exactly what those names are. 75.40.137.93 (talk) 10:33, 23 February 2012 (UTC)[reply]

RANSAC number of iterations[edit]

In the article on RANSAC it is said that the k (number of iterations required) in this formula

k={\frac {\log(1-p)}{\log(1-w^{n})}}

is for the case where the n points are selected independently and that "the derived value for k should be taken as an upper limit in the case that the points are selected without replacement". Is that saying that k, as calculated by this formula is slightly bigger than it needs to be or smaller than it needs to be? In my algorithm I need to select without replacement and I want to play it safe, so is k large enough? 41.164.7.242 (talk) 11:21, 14 February 2012 (UTC) Eon[reply]

Slightly larger than it needs to be. If you sample without replacement, then the likelihood that a later iteration selects a set of points which are all inliers is higher than for earlier iterations. If you sample with replacement, it's constant over all iterations. 131.111.255.9 (talk) 17:07, 14 February 2012 (UTC)[reply]

I'm pretty sure the article talks about replacement after each datum selection within a single iteration. After each iteration the state (other than a random seed) resets. Hence neither the "with replacement" nor the "without replacement" scenarios they are referring to has the current iteration affecting future iterations. What puzzles me is that it instinctively feels like k should be larger if one (like I have to do) doesn't do replacement. 196.215.142.253 (talk) 20:16, 14 February 2012 (UTC) Eon[reply]

Diophantine equations[edit]

I'm in the throws of doing Project Euler problem 66 which involves solving x^2 - D*y^2 = 1.

I have ascertained that continued fractions of D^0.5 are involved and it often works. You evaluate the continued fraction till just before the repeat

EG 7

7^0.5 = [2;1,1,1,4]

2+ 1/ (1+ 1/ (1+ 1/ 1))) = (I've put cont fract coeffs in bold)
2+ 1/ (1+ 1/ (1+ 1))) =
2+ 1/ (1+ 1/ 2)) =
2+ 1/ (3/ 2)) =
2+ 2/3 =
8/3

And we have 8^2 - 7*3^2 = 64 - 7*9 = 64-63 = 1. OK

EG 19

19^0.5 = [4;2,1,3,1,2,8]

4+ 1/ (2+ 1/ (1+ 1/ (3+ 1/ (1+ 1/2 )))) =
4+ 1/ (2+ 1/ (1+ 1/ (3+ 1/ (3/2 )))) =
4+ 1/ (2+ 1/ (1+ 1/ (3+ 2/3 ))) =
4+ 1/ (2+ 1/ (1+ 1/ (11/3 ))) =
4+ 1/ (2+ 1/ (1+ 3/11 )) =
4+ 1/ (2+ 1/ (14/11 )) =
4+ 1/ (2+ 11/14 ) =
4+ 1/ (39/14 ) =
4+ 14/39 =
170/39

And we have 170^2 - 19*39^2 = 28900 - 19*1521 = 28900-28899 = 1. OK

But it doesn't seem to work for 13

IE 13

13^0.5 = [3;1,1,1,1,6]

3+ 1/ (1+ 1/ (1+ 1/ (1+ 1/ 1))) =
3+ 1/ (1+ 1/ (1+ 1/ (1+ 1))) =
3+ 1/ (1+ 1/ (1+ 1/2)) =
3+ 1/ (1+ 1/ ( 3/2)) =
3+ 1/ (1+ 2/3) =
3+ 1/ ( 5/3) =
3+ 3/5 =
18/5 =

And we have 18^2 - 13*5^2 = 324 - 13*25 = 324-325 = -1. WHY -1?

What am I doing wrong? -- SGBailey (talk) 11:26, 14 February 2012 (UTC)[reply]

You might find the article on Pell's equation useful with this. Basically the problem you're running up against is that the period for the continued fraction for √13 is odd length and the technique you're truing only works for even period lengths. There is a simple work-around though: just use two periods instead of one to force the length to be even.--RDBury (talk) 12:24, 14 February 2012 (UTC)[reply]

Thanks - worked a treat. -- SGBailey (talk) 16:06, 14 February 2012 (UTC)[reply]

Planar graphs and coloring[edit]

I was trying to read the following proof I found on the internet and could not understand the first line. The graph in question is planar (and that's all we know about it):

" Without loss of generality, we may assume that all the faces of our graph are triangular, because adding edges just makes a graph harder to color. (We are coloring vertices.) Let V, E and F be the number of vertices, edges and faces. Every edge is in two faces, and every face has three edges, so F=(2/3)E. We have V−E+F=2 by Euler's relation, so V=E/3+2. Since the sum of all vertex degrees is 2E, the average degree of a vertex is 2E/V=(2E)/(E/3+2)<6. "

My question is how can one assume without loss of generality that the faces of our graph are triangular? Thanks-Shahab (talk) 14:55, 14 February 2012 (UTC)[reply]

Suppose you had a face that wasn't triangular; maybe a square. Add an edge going across it, dividing the face into two triangles. Since adding edges makes coloring harder, if you can color the new graph, you can color the old graph, and you've gotten rid of one non-triangle face. Repeat for all faces.--121.74.118.113 (talk) 15:08, 14 February 2012 (UTC)[reply]

(edit conflict) What they are claiming is that assuming triangular faces does not affect their claim about coloring planar graphs. The rationale is that adding edges makes a graph harder to color, because more edges means more conditions for each vertex's color to satisfy. Look at it this way: if given a graph with non-triangular faces, add in edges until it has all triangular faces. Then, apply the coloring algorithm (if it's a constructive proof), or convince your self that the valid coloring exists (if the proof is existential). When you are done with the coloring, you can remove the edges that you added, and still have a valid coloring for the original graph. Does that help? SemanticMantis (talk) 15:10, 14 February 2012 (UTC)[reply]

It does. Thank you both-Shahab (talk) 15:16, 14 February 2012 (UTC)[reply]