Wikipedia:Reference desk/Archives/Mathematics/2007 February 28

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 28

Finding first digit

Say, I'm doing a subtraction problem I really don't want to spend time on. Like 1235232 and 499876. Or if I was multiplying, adding, or dividing them, how could I find the digit to the far left? Thanks! [Mαc Δαvιs] X (How's my driving?) ❖ 02:14, 28 February 2007 (UTC)

What was your question again? Is it, how do I find the left most digit if I subtract 499876 from 1235232? 202.168.50.40 03:33, 28 February 2007 (UTC)

This is subtracting from left to right instead of right to left. For instance lets subtract 103 from 892. 8 - 1 = 7, but we need to check to see if we need to "borrow" from that 7. ok, 9-0, so we don't have to go any further to find the left most digit.

Generally, I think the algorithm is something as follows. If you want to do quick arithmetic, make these instructions make sense to you, don't just try to memorize them. I'm no expert at quick math, but I've come across this a time or to and occasionally try to use something like this when I'm figuring subtraction. BTW, these instructions are off the top of my head and may possibly be incorrect in some sense... (I already see one problem; this algorithm repeats indefinitely for subtraction of 100 minus 1 ... it continues to try to solve 100 minus 001 indefinitely. So it needs a bit of rehashing.)

Algorithm try 1.

1. Write each number with zeros extended to the left until both of their decimal notations are equal in length I.E. if 9359 is to be subtracted from 10072, write 9359 as 09359.
2. subtract the first two digits and make note of the subtraction call this R (this example, R = 1-0 = 1).
3. subtract the next two digits and call this S (if they exist, otherwise you're done) if S is negative, you will have to set R <- R - 1 and S<- 10 + S (Eg. if S = -4 then S becomes 10-4 = 6) Now If S is 0 or R is 0, you will have to solve the problem RSxx - yy where xx and yy are the remaining digits to be subtracted, truncating unecessary zeros as needed. Here I'm using the notation RSxx means $R*10^{(}d+1)+S*10^{d}+xx$ where d is the respective power d for digit S (sorry there's a better word for it). Otherwise, you've already found the left most digit R.

With 10072 minus 9359 we have

1. step 1 compute as above 10072 "minus" 09359
2. step 2 R <- (1 - 0) = 1
3. step 3 S <- (0 - 9) = -9, then R<-0 and S<- 1
4. solve instead 1072 - 359
5. step 1 compute as above 1072 "minus" 0359
6. step 2 R <- (1 - 0) = 1
7. step 3 S <- (0 - 3) = -3, then R<- 0 and S = 7
8. solve instead 772 - 59
9. step 1 compute as above 772 "minus" 059
10. step 2 R <- (7 -0) = 7
11. step 3 S <- 7-5 = 2
12. since S and R <> 0 left most digit is 7 and its in the hundreds place.

As you can see, the algorithm terminates before you've subtracted the whole number. But it depends upon the numbers being subtracted. Also, anytime R>1 you know that the left most digit is going to be either R or R-1 and it will have the same decimal place. Work on that a bit, maybe you can fix this algorithm's logical bug. You can probably fix it by introducing a R_old which holds the digits that may accumulate and also noting somewhere through each iteration at which decimal place you are in the subtraction.

I'm not going to work on it any further, as although I know I could fix it to where a computer could make it work easily enough, to make it human workable would take more work than I can afford at the moment.

I'm not sure if there's a good left digit finder for multiplication (division as it is taught in schools is left to right anyway, right? its been so long since I've actually done long division though.). You can always start from the left to right by moving in a criss cross pattern and stop once you can be sure you're within a certain percentage of the most accurate, correct answer, as in

345 * 678 = 3*6*10000 + (3*7 + 4*6)*1000 + (3*8 +4*7+ 5*6)*100 + (4*8 + 5*7)*10 + 5*8(1)

and evaluate that from left to right, stopping when you feel satisfied.

Root⁴(one) 07:08, 28 February 2007 (UTC)

´how many miles are there in a kilometer? ´´´´

I looked everywhere in the internet and I can not find the answer. I am frustrated and I need to know as soon as possible. Please help me!!!—Preceding unsigned comment added by 201.202.137.206 (talk • contribs)

• 0.621371192 miles, give or take, see also mile & kilometer--VectorPotential^Talk 16:35, 28 February 2007 (UTC)

for future reference you can just 'search' in google in a 'calculation' like format...i.e. a google search of '1 mile in Km' will return (http://www.google.com/search?client=safari&rls=en&q=1+mile+in+km&ie=UTF-8&oe=UTF-8). This works for many calculations and can be very useful. ny156uk 17:12, 28 February 2007 (UTC)

You really need to work on your search skills. If you search for the title of this section, 'how many miles are there in a kilometer', the answer is immediate. --KSmrq^T 17:49, 28 February 2007 (UTC)

Go to www.google.com then type in "miles kilometer". The very first result is

kilometers to miles conversion calculator - length @ metric ... kilometers to miles conversion calculator, km, mile - length @ metric conversions . org.

www.metric-conversions.org/length/kilometers-to-miles.htm

- 20k - Cached - Similar pages

202.168.50.40 20:29, 28 February 2007 (UTC)

You searched everywhere in the internet? Well, maybe you should check to see if your eyes are open first before typing it in Google or Yahoo. [Mαc Δαvιs] X (How's my driving?) ❖ 20:28, 1 March 2007 (UTC)

Sequences derived from Fibonacci sequence.

I have found a new way to utilize the Fibonacci sequence and I would like to have opinions and/or help in publishing this on Wikipedia.

I have reduced the Fibonacci sequence to one digit (ex. 13=1+3=4). I have then seen that ones we reach the 24th digit of the Fibonacci sequence, the 24 numbers repeat themselves (ex. 25th number (reduced) is 1, the 26th is 1, the 27th is 2... etc.

This is the full sequence: 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 9, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 9.

From here I copied and added a second sequence below the first but starting in the middle of the first (13th number: 8).

I soon realized that the numbers between top and bottom sequence always add up to 9. Nines would be lined up together.

1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 9, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 9. (It seems Wikipedia doesn't allow for correct alignment).

8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 9, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 9.

If we can find the Fibonacci sequence in nature and also it's derived 'golden ratio', I wonder if this mathematical beauty is at the base of some other sequencing in nature... I actually believe it's only time before it will be found...

Also, I noticed a interrelation between the pairs. For example, the 7-2 pair is spaced by 5 pairs from the other 7-2 pair and 7-2=5 (between two 9 pairs). The 6-3 pair is spaced by 3 pairs and the 5-4 pair is spaced by 1. I have created an excel sheet in which I've vertically lined up the double sequence and assign a color for each number. It is very beautiful and harmonious. 68.163.230.21 16:10, 3 March 2007 (UTC)

To answer the publishing question, as far as "publishing it on Wikipedia", that wouldn't be allowed as it would be publishing original research, violating WP:NOR. You'd have to have your findings published by a reliable publisher first. Still, kind of a neat pattern. Dugwiki 20:50, 28 February 2007 (UTC)

About the first thing you mentioned, taking the sum of the digits of a number, etc. (like what you are doing) is equivalent to taking the number modulo 9 (since 10 is congruent to 1 modulo 0, and consequently any power of 10 is also 1 modulo 9), except that it should say 0 instead of 9. It is well known that the Fibonacci sequence modulo any number repeats, with a period known as the Pisano period (perhaps this should be mentioned on the Fibonacci number article). The 9th Pisano period is indeed 24. As for the other thing, it might just be a coincidence that the thing after the 0 (9) in the middle is an 8 (= -1 mod 9), and so the second half of the sequence is a repeat of the first but negative. --Spoon! 21:57, 28 February 2007 (UTC)

You know, I'm not sure this is actually just a coincidence. Take a look at the same sort of sequence when you look at the Fib series mod 7, for example. You get the repeating subsequence:

1, 1, 2, 3, 5, 1, 6, 0,

6, 6, 5, 4, 2, 6, 1, 0

Notice that each column adds to 7 or 0 (mod 7). I wouldn't be surprised if this works for any prime modulo. Dugwiki 20:52, 1 March 2007 (UTC)

It doesn't. Consider 5:

1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0

similarly for any prime>3 which is a Fibonacci number Algebraist 22:48, 2 March 2007 (UTC)

More on the pattern. Let's say you're looking at the series mod M for some natural number M, and that the n'th member of the series $F_{n}$ equals 0 mod M. Then you have $F_{n+1}=F_{n}+F_{n-1}=F_{n-1}$ and $F_{n+2}=F_{n+1}+F_{n}=F_{n+1}=F_{n-1}$. In other words, once you hit 0, you'll always get two of the same number in a row, which if that number is M-1 will mirror the start of the series "1, 1". Dugwiki 20:13, 2 March 2007 (UTC)

Interesting RIDDLE.. needs mathematical solution

HERE IS THE RIDDLE..
if 1 chick costs 5 cents, 1 hen costs 1 dollar and 1 cock costs 5 dollars..and you're asked to buy 100 units consists of these 3 kinds with exactly 100 dollars, which variation of them can agree with this condition??
I've been told this riddle and its answer, but i want to know if there is a possible way to conclude this answer mathematically ??!!
the answer is (80,1,19) consecutively.......thanx in advance

What an offensive question! deeptrivia (talk) 21:54, 28 February 2007 (UTC)

You can use a linear Diophantine equation. Let x = # of chicks, y = # of hens, then you want

$5x+100y+500(100-x-y)=10000$

This simplifies to

$99x+80y=8000$

You can use the extended Euclidean algorithm to solve this. You get

$-21*99+26*80=1$

Multiply both sides by 8000 to get

$-168000*99+208000*80=8000$

Or x = -168000, y = 208000

But this is not unique. For every increase of 80 in x and decrease of 99 in y, you get another valid solution. Now I assume you want solutions such that x, y, and 100-x-y are all nonnegative. So the valid solutions are:

(0, 100, 0)

(80, 1, 19)

-- Spoon! 22:13, 28 February 2007 (UTC)

Thank you Spoon, but can you show the details of the step of using extended Euclidean algorithm, pls? (which led to: -21 * 99 + 26 * 80 = 1)

Check out Extended Euclidean Algorithm#External links; at least one of those should do it for you. —Keenan Pepper 06:46, 1 March 2007 (UTC)

Nice. I would have gone with a less high-tech solution. I was thinking: Since hens and cocks can give only whole-dollar values, and the goal is a whole-dollar value, chicks must be some multiple of 20, which narrows it to 6 options. (Chicks/20)+hens must be a multiple of 5, which narrows it down further, and then cocks must make up the difference. It doesn't take long to go through all the options from there. I like Spoon's idea better, though. Black Carrot 07:01, 1 March 2007 (UTC)

Make sure you remember to include at least one cock for every chick. [Mαc Δαvιs] X (How's my driving?) ❖ 20:25, 1 March 2007 (UTC)

*groan* –King Bee ^{(T • C)} 20:29, 1 March 2007 (UTC)

That's what she said. Black Carrot 06:24, 2 March 2007 (UTC)

Archiving

Would anybody who knows how to archive the Ref-Desks be able to assist in gettting the oldest day on each desk down to Feb 21, so that RefDeskBot can resume normal operation? Thanks for your help (you may be able to collaborate here if others are doing the same). Martinp23 22:30, 28 February 2007 (UTC)

I've archived WP:RD/MA through February 20.  --Lambiam^Talk 02:41, 3 March 2007 (UTC)

Pairwise permutation differences

I've posted this on both sci.math and alt.sci.math.combinatorics without getting a single reply. I suppose the question I want answered is "Does this problem ring any bells with anyone"? Before my newsgroup postings, I would have bet money on my having rediscovered something well-known, but now I'm starting to wonder. So ...

... whilst designing an experiment recently, I evolved the following problem:

Given the sequence S of natural numbers 1...N (N odd), is it possible to find a permutation p(S) such that the pairwise difference S-p(S) gives the integers -(N-1)/2, ...,-1,0,1, ...,(N-1)/2?

At the time, I was specifically interested in S = 1...7.

It wasn't immediately obvious to me whether a solution was possible, and if it was, whether or not it would be trivial or obvious with hindsight. I shared the problem with a colleague, and we both set about independently trying to find a solution - which we each did, in a few minutes. We used a different strategy and came up with a different solution: his strategy also worked for the simpler case S = 1,2,3, whereas mine did not.

I then investigated the problem systematically using Mathcad, and determined somewhat to my surprise that there were in fact 24 possible solutions. Clearly, every solution must have one member of S that remains fixed, to give the value 0. My colleague had fixed the starting value 1, whereas I had fixed the central value 4. It turns out that for S = 1...7, there are solutions for every choice of fixed value. Some choices are more "difficult" than others. Fixing the value 1 or 7 gives six possible solutions each. Fixing the value 2, 4, or 6 gives four possible solutions each. Fixing the value 3 or 5 gives two possible solutions each.

The solutions divide into three classes: those consisting, in addition to the fixed point, of one six-cycle, two three-cycles and three two-cycles. From my dim memory of group theory, this sounds like Sylow's theorem is lurking somewhere.

The simplest case S=1,2,3 shows that there are not always solutions for every choise of fixed value.

It seems certain that the general version of this problem has been studied, possibly indirectly.

Is it necessarily the case that the number of solutions increases hugely as N increases, or are there "interesting" values of N for which solutions are uncommonly sparse, or require a restricted choice of fixed value - or even are non-existent?

Spargeus 22:39, 28 February 2007 (UTC)

I have seen things like this in the 'Problems' section of American Mathematical Monthly and Mathematics. I remember a person named Emeric Deutsch at a university in New York who was expert in these.Rich 23:10, 2 March 2007 (UTC)

I can show that there's at least one solution for every (odd) value of N. This solution consists of (N-1)/2 two-cycles plus the fixed point. That is, p(p(S))=S for all S. This simplifies the problem a bit: we must now find (N-1)/2 pairs of numbers between 1 and N, without repeating a number, such that the differences between the pairs gives us each of the values between 1 and (N-1)/2. (So, for example, if we "pair" 1 and 6, that gives us p(1)=6, and p(6)=1, which gives us both +5 and -5 as differences.)

The method is simple: divide the sequence into halves, with the middle number (arbitrarily) in the lower half. Thus, the lower half has one more number than the upper half. Now, within each half, pair the outermost numbers, then the next outermost numbers, and so forth, until all possible numbers are paired. One half gives you odd numbers as differences, and the other half gives you the even numbers (which is which depends on the value of N mod 4). As an example, here's the solution given by this process for N=17:

p(1)=9 p(9)=1

p(2)=8 p(8)=2

p(3)=7 p(7)=3

p(4)=6 p(6)=4

p(5)=5

p(10)=17 p(17)=10

p(11)=16 p(16)=11

p(12)=15 p(15)=12

p(13)=14 p(14)=13

Or, to express it formally, p(S)=(N+3)/2-S for S<=(N+1)/2, and p(S)=(3N+3)/2-S for S>(N+1)/2. Chuck 23:51, 2 March 2007 (UTC)

That's a very pretty solution (actually, it's two solutions, depending which half we "arbitrarily" assign the middle number to)! I'd love to know how you came up with it. I particularly like the fact that it's a constructive proof, not just an existence proof. As you say, looking for (N-1)/2 2-cycles simplifies the problem a bit - it's the logical place to start. Now we know that there is always at least one pair of solutions, I'm wondering if the method gives any clues as to how we might go about identifying "higher-order" solutions.

I'm sure there must be a Sylow thing going on - any solution must consist of a set of equal-order cycles - so if the order is O, there are C such cycles and OC = N-1. So O and C must always divide (N-1). I can't prove that, it just seems obvious, and my investigation of N=7 provides a little evidence. But even if it is the case, it's only a necessary condition, not a sufficient one.

O=2 is always such a divisor, so it's neat that there is always a corresponding solution. C=2 is also always such a divisor, so it would be really neat if there was also always a corresponding solution. I don't see any promising line of enquiry to extend your method from 2-cycles to [(N-1)/2]-cycles, though.

Spargeus 12:11, 4 March 2007 (UTC)

I can't really say how I found that - I was just playing around with the problem and trying to see any patterns in some solutions which might lend themselves to a general solution, and lo and behold, I found one.

It's not the case, however, that all solutions must consist of a set of equal-order cycles (in addition to the one 1-cycle). It seems to be true for all N up to N=7, but not N=9 (or, I presume, higher N). One way of attacking the problem is to note that all the differences represented in a given cycle must add up to 0. The only way to split up N=7 into unequal cycles (given that we must have exactly one 1-cycle) would be cycles of 1, 2, and 4. There's a limited number (three) of ways to split up the integers -3 to 3 into groups of 1, 2 and 4 numbers, such that the sum of each group is zero, and it's not too hard to show that you can't get a permutation p(S) that correspond to any of those partitions.

But with N=9, one way of partitioning the differences into unequal cycles, given those restrictions, would be {0}, {1, 2, -3}, {-1, -2, 3}, {-4, 4}. And there is (at least) one permutation corresponding to that partition:

p(5)=5

p(9)=8, p(8)=6, p(6)=9

p(1)=2, p(2)=4, p(4)=1

p(3)=7, p(7)=3

(Actually, there's at least two permutations, because you can reverse the orientation of the two 3-cycles.)Chuck 19:51, 5 March 2007 (UTC)

P.S. I'll also note that the above permutation for N=9 is one of a class of what I think should be called "symmetrical" solutions, which can formally be defined by saying that for all S, N+1-p(S)=p(N+1-S). Note that any non-symmetrical solution necessarily implies the existence of a corresponding "mirror-image" solution - let's call that q(S), and it can be defined as q(S)=N+1-p(N+1-S). Chuck 20:26, 5 March 2007 (UTC)