Mathematics desk
< August 10	<< Jul \| August \| Sep >>	August 12 >

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 11[edit]

decimals[edit]

are decimals integers? Are decimals rational numbers? How useful are realnumbers? — Preceding unsigned comment added by 112.198.64.88 (talk) 02:35, 11 August 2013 (UTC)[reply]

See Decimal. In general, a decimal number is not an integer, but they can be, e.g. 2.0. A decimal number may or may not be a rational number. Real numbers are very useful. Bubba73 ^{You talkin' to me?} 04:13, 11 August 2013 (UTC)[reply]

Does 2.0 count as an integer ? The integer 2 means exactly 2, while 2.0 means something more like 2.0 ± .05, at least in an engineering sense. Also, they are used for different things. You can have 2 cats, but not 2.0 cats (unless they are new and improved). StuRat (talk) 05:15, 11 August 2013 (UTC)[reply]

You have a point there. If it is exactly 2.0 then it is an integer. If it is a measurement, then it is not. Bubba73 ^{You talkin' to me?} 05:21, 11 August 2013 (UTC)[reply]

<pun> point </pun> - Well played. - ¡Ouch! (^{hurt me} / _{more pain}) 11:45, 16 August 2013 (UTC)[reply]

And yes, decimals are rational, which means they can be expressed as the ratio of two integers. For example: 1.2345 = 12345/10000. StuRat (talk) 05:19, 11 August 2013 (UTC)[reply]

Not if it has an infinite number of non-repeating digits after the decimal point. Bubba73 ^{You talkin' to me?} 05:21, 11 August 2013 (UTC)[reply]

But would that be considered a decimal ? Pi, for example, can be approximated as a decimal, but isn't truly a decimal, is it ? StuRat (talk) 05:23, 11 August 2013 (UTC)[reply]

You can't list an infinite number of digits but it has an infinite number of digits. Bubba73 ^{You talkin' to me?} 05:55, 11 August 2013 (UTC)[reply]

But the Q remains, is the real value of pi actually a decimal ? StuRat (talk) 08:07, 11 August 2013 (UTC)[reply]

I think so. A decimal number is really our way of writing numbers, apart from being integer, rational, or real. See decimal#Real numbers. Bubba73 ^{You talkin' to me?} 10:57, 11 August 2013 (UTC)[reply]

Every real number has a sequence of digits corresponding to an infinite sum that converges on it, so even if you can't compute the digits (and for pi, you can), they are still a decimal. But, moreover, if that weren't the case, then what would make rationals decimals? You can't write out all the 3's in 1/3 either; or even all the 0's after the 1 in 1/10th. You can suppress them using a symbol indicating "3's from here out", but, that's just shorthand.Phoenixia1177 (talk) 04:43, 13 August 2013 (UTC)[reply]

Real numbers are also incredibly useful, being used extensively in science, math, computer programming, and pretty much every field of human activity, etc. StuRat (talk) 05:21, 11 August 2013 (UTC)[reply]

Yeah, real numbers are the real deal, man! —SeekingAnswers (reply) 06:40, 11 August 2013 (UTC)[reply]

Can "n choose 4" be squarefree infinitely often?[edit]

The largest i've found so far is "2084 choose 4" = 521*2083*347*2081. Thanks!76.218.104.120 (talk) 12:03, 11 August 2013 (UTC)[reply]

Almost certainly. I don't know whether it follows from known results. It happens frequently in practice so the challenge for large cases is to prove it, for example by knowing the factorization of 4 large consecutive numbers. I happen to have a record page about the largest consecutive factorizations. At [1] is a case with 1104-digit numbers n to n+3. The formula for the numbers is a little complicated. At the time it was part of the largest known case of 6 consecutive completely factored numbers, found by David Broadhurst in 2007.[2] PrimeHunter (talk) 13:38, 11 August 2013 (UTC)[reply]

Thanks! Hmm, then i foolishly lowballed my question. I could have asked, for fixed positive k, does the sequence: {(n choose k)}, for n=k to infinity; have infinitely many squarefrees? I could do some of this myself on Wolfram Alpha-factorization of (large k) large consecutive numbers76.218.104.120 (talk) 22:10, 11 August 2013 (UTC)[reply]

It would follow from Dickson's conjecture. For any k there would be infinitely many N such that (N-i)/i is prime for i = 1..k. Then ((N-1) choose k) would not only be squarefree but be a product of k primes. In 2003 I computed [3] N=7272877497848202240 is the smallest solution to this for k=14. So (7272877497848202239 choose 14) is a product of 14 primes: 519491249846300159 * 559452115219092479 * 606073124820683519 * 661170681622563839 * 727287749784820223 * 808097499760911359 * 909109687231025279 * 1038982499692600319 * 1212146249641367039 * 1454575499569640447 * 1818219374462050559 * 2424292499282734079 * 3636438748924101119 * 7272877497848202239. If we only want it to be square-free then it's trivial to find solutions for much larger k. PrimeHunter (talk) 23:58, 11 August 2013 (UTC)[reply]

I counted 360 cases between 2000 and 3000. In fact 2085 choose 4 = 3 * 5 * 139 * 347 * 521 * 2083. I suspect that the proportion of such numbers approaches a constant. Heuristically, the amount that gets thrown out for a given p>4 is 4/p², which forms a convergent series.--RDBury (talk) 14:07, 11 August 2013 (UTC)[reply]

Interesting. That 36% makes me think of 1/e, although admittedly i've had e on the brain lately! Maybe mobius mu of(n choose 4) would break into an intersting distribution.76.218.104.120 (talk) 22:02, 11 August 2013 (UTC)[reply]

The expected ratio is

{\frac {3}{4}}\times {\frac {19}{27}}\times \prod _{i=3}^{\infty }{\frac {p_{i}^{2}-4}{p_{i}^{2}}}

. It's around 0.359669, not 1/e = 0.367879... PrimeHunter (talk) 00:28, 12 August 2013 (UTC)[reply]

Good information, thanks!76.218.104.120 (talk) 21:58, 13 August 2013 (UTC)[reply]

NP-Complete?[edit]

What is the name of the following problem, and is it known to be NP-complete?:

Does there exist a 0,1 vector x such that Mx = 1, where M is a given 0,1 matrix and 1 is a vector of ones?

Duoduoduo (talk) 15:01, 11 August 2013 (UTC)[reply]

Garey & Johnson call this ZERO-ONE INTEGER PROGRAMMING, listed in MP1 of Computers and Intractability. See Linear programming#Integer unknowns.--RDBury (talk) 23:41, 11 August 2013 (UTC)[reply]

Linear programming#Integer unknowns says integer programming problems are in many practical situations (those with bounded variables) NP-hard. [my bolding]. I'm wondering whether this particular subset of ILP problems is still NP-complete. My copy of Garey and Johnson is in transit right now so I can't check there -- do they specifically refer to this type of ILP problem? Thanks. Duoduoduo (talk) 16:44, 12 August 2013 (UTC)[reply]

Yes. "Variant in which all components of y [the solution vector] belong to {0,1} (ZERO-ONE INTEGER PROGRAMMING) is also NP-complete, even if each b [the constant column], all components of each x [coefficient vector] and all components of c [objective function] are required to be in {0,1}." The paper cited is S. Sahni, "Computability and related problems" SIAM J. Comput. 3, 262-279 (1974). One thing that confuses me about this is that if any of the b's are 0 then it trivially eliminates any variable involved in that constraint, so why not just require all b's to be 1?--RDBury (talk) 00:06, 13 August 2013 (UTC)[reply]

Thanks. You're right about the b vector -- any zeroes make it trivial to reduce the size of the problem by setting the relevant y's equal to zero. I'm sure they were just trying to be succinct in their wording since all the others they mentioned are in {0, 1}. Duoduoduo (talk) 16:05, 13 August 2013 (UTC)[reply]