Fork me on GitHub
Math for the people, by the people.

User login

topic entry on real numbers

Type of Math Object: 
Topic
Major Section: 
Reference
Groups audience: 

Mathematics Subject Classification

54C30 no label found26-00 no label found12D99 no label found

Comments

A frog is hopping on the integers from minus infinity to plus infinity. Each hop is chosen at random (with equal probability) to be either +2 or -1. So the frog will make steady but irregular progress in the positive direction. The frog will hit some integers more than once and miss others entirely. What fraction of the integers will the frog miss entirely?

zero? depends on the frog?

i am not sure, just playing along with the riddle.

but i have a frog that does this and doesn't miss a single integer.

without loss of generality(i love this sentence) all frogs in time 0
are standing exactly on 0.
now if she hops +2 -1... from the dawn of time(-inf) until her
full self-realization(+inf) it is easily shown my froggie doesn't miss
a single integer.

so this is probably not the "exact" answer...but hey,
it feels identical to the question , what are the chances that a random
walk +1,-1 on the integers will return to the origin.

.. another direction would be this, given that your frog is at a
certain integer n , what are the chances that she will reach n+1?
compute this and the answer is probably 1-this .

Tsurbaba,

Can you please tell me what fraction of integer would be hitmore than once?

SInce you explicitly asked me for help, I will at least describe
part of the answer. Before worrying about probability, let us first
adress the issue of possibility --- that is to say, what can the frog
do irregardless of whether a certain outcome is at all likely.

Let S be the set of all integers which the frog ever visits. Then
there are four possbilities which we shall examine. For convenience,
we assume that the frog starts on zero.

I. S is bounded from above and below.

In this case S is fininte. This case is certainly possible
because, for instance, the frog could go

0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 .....

In this case, an infinite number of integers are missed and only
a finite number are attained so the proportion missed is 1.

II. S is bounded from above but unbounded from below

Since the only way for the frog to go to the left is one step at
a time, the frog will have visited all negative integers and it
is assumed that the frog sees only a finite number of positive
integers. In this case, all positive integers larger than a
certain bound are missed as well as possibly a finite number of
positive integers smaller than that bound so the proportion of
integers missed is 1/2.

III. S is unbounded both from below and from above.

In this case, it turns out that S contains all the integers so
that the proportion of integers missed is 0.

IV. S is bounded from below but unbounded from above.

In this case, it turns out that the proportion lies between 1/2
and one, providing that it is well-defined.

Since it is late now, I will stop now. If you are interested
in knowing more about the reasoning behind the last two assertions,
I will be glad to provide it. Also, in order to go from
possibility to probability, you will need to consider the
measure on the set of random wals and figure out the measures of
the sets of walks satisfting the four conditions.

Thanks a lot rspuzio, I am really thankful to you as you have been always helpful for any dicussion.

I understood all your four assertions but regarding the last assertions, I am getting it 1/2. can you please tell me how are you getting between 1/2 and 1 and what is the exact answer?

How do you count the integers missed? There seems to be two ways of looking at this:

1. the # of integers missed is the number of integers on the entire integer line that the frog has never visited.

2. the # of integers missed within the "scope" of the path. What this means can be loosely interpreted as follows: if the frog takes n positive jumps, then the scope of this path is [0,2n], since the frog starts from 0, and has gone as far as 2n. The # of integers missed in this "sample path" is n. On the other hand, if the frog takes n negative jumps, the scope is [-n,0], and the frog eventually lands on -n. In this case, the number of integers missed by the frog is 0. So the scope can be defined as the range [a,b] that that frog's jumps have covered, and the number of integers missed is counted with [a,b]. Of course, as n goes to infinity, [a,b] could become be an infinite interval as well.

CWoo,

your first point is right i.e. the # of integers missed is the number of integers on the entire integer line that the frog has never visited

regard rspuzio message, i am not en expert in math
but i know my frogs..

option ii is impossible, since any frog must satisfy that
the average hop is 1 , as the counting goes to infinity,with-out regard
to the starting time.
let h(t) be the hop in time t.
then sum(i=t0;i<t;i++) of h(i)/(t-t0) equals one as t goes to infity, this is the meaning of
equal probablity for h(t) = 2 or h(t)=-1;

now as for your question. the way you put it, well i have to say again it depends on the frog.
i believe this is a question from probablity course no?
so you might want to rephrase your question,

instead of frogs lets speak of Toads, to make things more clear.
let T be the set of all toads and let t be in T,
and let g be a function such that
g(t) = the fraction of integer missed by toad t.

then you are looking for the "average" of g.

now if you can compute the probability to reach from integer n
to integer n+1 using the general hoping toad, which i beleive is a slightly modified version of the computation, what are the chances that a random walk returns to the origin(which you probably learned or can get a copy of the proof) , now if this comes out 1 , then you are
finished because then you managed to prove that the average fraction
would be zero.
if not then...there must be someone here who knows some math.

In my reply, I was discussing only possibility, not probabilibty.
It well might be the case that some of these options, though
possible, happen to be a subset of the measure space whose
measure is zero, hence are not probable even though they are possible.

can anyone please direct me to final answer?

Hang on --- I will post more when I get some time if someone else
does not do so first.

Are you looking for an exact answer? Otherwise, this can be done via a simulation of the random walk process.

I am looking for an exact answer.

Can somebody please post an exact detailed answer?

Refreshing the post so that some one's attention is drawn to answer it

Refreshing the post so that some one's attention is drawn to answer it.
Can anybody please help?

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

The sum of the digits of 2^1000 is 1366.

I wrote a program to find this, but the program never threw a result as there are lots of calculations involved in this and the processor could not cope up.
Can you tell me how did you find this answer?

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that the 7th triangle number, 28, is the first triangle number to have over five divisors.

Which is the first triangle number to have over five-hundred divisors?

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

I thought I was cheating when writing a program. You should state explicitely that computer aid is allowed.

What kind of programs do you write? I use Visual C for speed, or Matlab for easier life.

Since the number of digits in 2^1000 is 302, I define an array a little bit bigger. Each element of the array represents a decimal digit. The first element (least significant digit) is set to 1 and all the others to 0. All what is needed now is to program a loop executed 1000 times, to multiply the array by 2. The trick, to save time, is to multiply only the significant digits, not the whole array. Starting with a digit count of 1, the count is incremented every time we get a carry out of the most significant digit.

As a result, I get the answer in no measurable time (much less than 1 second), even with Matlab which is an interpreter, not a compiler.

By the way where do you get these problems? do you invent them yourself?

PARASHAR writes:

> I wrote a program to find this, but the
> program never threw a result as there are
> lots of calculations involved in this and
> the processor could not cope up.

Here's a function (in Common Lisp):

(defun decimal-sum-of-digits (n)
(let ((sum 0))
(loop for char across (write-to-string n) do
(incf sum (- (char-code char) 48)))
sum))

Now doing

(decimal-sum-of-digits (expt 2 1000))

gives the answer 1366 instantly (on a 2GHz machine), even though this is rather inefficient and written in a slow language. Are you sure your program didn't just get stuck in an infinite loop due to a bug?

The longest Collatz sequence, for numbers below 100000, has a length of 525 and it starts at 837799. The computation time is 0.078 sec on an AMD64 machine running at 2Ghz.
The program, written in Visual C, uses a recursive function. Intermediate results are stored in large array to avoid repetitions. The recursion level reached 1233959.

A bug in the program reported the wrong recursion level; it is only 110. The result and computation time are correct.

Triangle number 12375 (12375 * 12376 / 2) has 576 divisors.
Computation time = 0.047 sec in Visual C.

Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.
For example, f(10)=5 since there are five different ways to express 10: 1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 and 2+8.
Describe, in a single sentence, the sequence {f(n)/f(n-1)} for positive integer n.
Show your proof to this sentence.

Hints:
i)2^{n-1}+2^{n-1}=2^n, (powerful!)
ii)f(2^n)=n+1. (n>0) e.g. 2^2=2^1+2^1=2^1+2^0+2^0 (finish!)
iii)n=2m+1 just contains *one* 2^0, so you cannot decomposing 2^1=2^0+2^0 in addition. e.g. 11=2^3+2^1+2^0=2^2+2^2+2^1+2^0 (finish)
I suspect this problem has an elegant solution by using modular theory.

Are you sure that something clever can be said about the series f(n)? As already noted by Perucho f(2^p) = p + 1, but also:
f(2^p - 1) = 1 and f(2^p + 1) = p

Betwen 2^p and 2^(p+1) - 1, the function starts at p+1, goes up and down in a quite irregular pattern, and terminates at 1; I wrote a program (cheating again) to plot the function from 1024 to 2047.

If something meaningful can be said about it, I'm waiting for the solution.

Well dh2718, what I said it was at first sight. I think this problem is not so easy. So I suggested a solution via modular theory or something like that, but I haven't experience in this area. Apparently combinatory also takes part. I think that those functions f should be important as one may representing n in base 2. Perhaps we must study n on the form
n=2^{m_1}+2^{m_2}+...+2^{m_k},
and then analyzing some combinatory about the exponent's difference (m_k-m_{k-1}), but I haven't studied this in deep. Nevertheless, it's very probable exists another better way. Maybe Chi could help us as he knows much about this kind of problems. (I guess!)
perucho

I just saw this problem on the IBM site Ponder This:

http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/August200...

Parashar, it would be fair if you had indicated your source.
This site suggests thate there is a closed formula for f(n), not just a recursion formula.

Hello dh2718,
I haven't said that it's a recursive formula. I'm just expressing n in base 2. In fact f(2^m)=m+1 is closed.
But anyway, I have thought a little deep this problem. In particular, I have considered n on the form
n=2^{m+k}+2^m,
and after some work I have arrived to the result
f(n)=k(m+1)+m.
For example,
m=4, k=3. Thus n=2^7+2^4=144, so f(144)=3(4+1)+4=19, with decomposition
1. 2^7+2^4, 2. 2^7+2^3+2^3, 3. 2^7+2^3+2^2+2^2, 4. 2^7+2^3+2^2+2^1+2^1,
5. 2^7+2^3+2^2+2^1+2^0+2^0, 6. 2^6+2^6+2^4, 7. 2^6+2^6+2^3+2^3,
8. 2^6+2^6+2^3+2^2+2^2, 9. 2^6+2^6+2^3+2^2+2^1+2^1,
10. 2^6+2^6+2^3+2^2+2^1+2^0+2^0, 11. 2^6+2^5+2^5+2^4,
12. 2^6+2^5+2^5+2^3+2^3, 13. 2^6+2^5+2^5+2^3+2^2+2^2,
14. 2^6+2^5+2^5+2^3+2^2+2^1+2^1, 15. 2^6+2^5+2^5+2^3+2^2+2^1+2^0+2^0,
16. 2^6+2^5+2^4+2^4+2^3+2^3, 17. 2^6+2^5+2^4+2^4+2^3+2^2+2^2,
18. 2^6+2^5+2^4+2^4+2^3+2^2+2^1+2^1,
19. 2^6+2^5+2^4+2^4+2^3+2^2+2^1+2^0+2^0, by copy/paste.
So, if this is not wrong, we now need find out a law (if that is possible) for
n= 2^m+2^{m+k_1}+...+2^{m+k_p},
or something like that, in order to express every n in base 2. So, if you want, you can helping. And yes, this is annoying but I don't know another way.
perucho

Perucho, your formula is correct; I salute you and wonder how did you reach it?

Here are other partial results:
Looking at the binary representation of the number n, if there is only 1 ZERO and all other binary digits are ONE, then f(n) = p + 1, where p is the number of ONEs preceding the ZERO.
Generalization: if there is only one block of q consecutive ZEROs preceded by p ONEs, then f(n) = pq + 1.

Maybe together we'll reach the complete solution?

Obviously, the key to this problem is binary representation (at IBM they think binary). So I re-formulate the problem:

The binary representation of a number n is:

n = b(m)*2^m + b(m-1)*2^(m-1) + ... + b(0)

The b coefficients can only be 1 or 0. Such a representation is unique (modular algebra). In the IBM problem, the coefficients are allowed to reach 2. Then, the representation is not unique any more and f(n) is the number of equivalent representations for n.

From a given IBM representation, we can get another one by the following operation:
substract 1 from a coefficent b(p) and add 2 to b(p-1), provided that this operation is allowed; that is b(p) > 0 and b(p-1) = 0.

From this observation we get immediately all the partial results we actually have up to now:

ONE followed by p ZEROs: f(n) = p + 1
all b are ONE: f(n) = 1
ONE followed by p ZEROs followed by ONE followed by q ZEROS:
f(n) = (p+1)(q+1)+ q (Perucho)
p ONEs followed by q ZEROs followed by r ONEs: f(n) = pq + 1

@dh2718

I am really sorry for not describing the source of this ptoblem as when I was posting this problem, I was in a hurry and I was just about to leave the state for some work and I came back today itself so I could not participate in the discussion.

@dh2718 and perucho

Let me draw your attention to the answer of this problem. The answer is that "the sequence {f(n)/f(n-1)} for positive integer n contains all possible non-negative fractions expressed in lowest terms and each exactly once"
But we need to prove this. How???

i.e. \{f(n)/f(n-1)\}=\{\mathbb{Q}_+\}.

@perucho,
sorry to say but I did not understood your notation, can you please write in simple format?

@dh2718 and perucho

Any inputs please?

It is not nice to announce the answer to a problem that others are trying to solve without warning them that you are doing so.

The sequence in question is the Calkin-Wilf enumeration of the rationals: http://www.math.upenn.edu/~wilf/website/recounting.pdf

Interesting paper ratboy. I could not find the answer. And yes, I thought on a kind of Fibonacci distribution but I didn't see the 2. I found some interesting results as
i)f(\sum_{k=0}^m 2^k)=1,
ii)f(\sum_{k=1}^m 2^k)=m+1,
and another ones, but these was not enough. I also tried to expand out
n=2^{k_m}+...+2^{k_1}, k_m>...k_1,
but I just got an annhilation resulting in an obvious identity.
I must confess that this problem was annoying for me.
Cheers,
perucho

does anyone know why,
if n is a natural number and
1<=i<j<=n,
the following expression
gcd((n!)i+1, (n!)j+1)=1, must be true ?

thanks and greetings, Wim

Let me rephrase that just to check that I understand correctly. For a given n, it is the case that 1 plus the factorial of n times some number i is coprime to 1 plus the factorial of n times any number j that is greater than i, but not greater than n.

So, picking small numbers out of a hat: n = 5, i = 3, j = 4. Then n!i + 1 = 361, and n!j + 1 = 481. 361 is 19 squared, and 481 is 13 times 37. For this particular case, your statement as I understand it checks out.

Have I understood your statement correctly?

Yes, this is correct. I would only add that i<j. is the statement generally true? and why?

it is an attempt to construct two coprimes from any natural number. when this is true, there is an infinite number of primes.

(alternative proofs for the Euclid proposition that there are infinite primes)

thanks for your reply,
Wim Schols

Hi,

Two hints:

1) If p>0 is prime and divides (n!)i+1, with i non-zero, then p is larger than n.

2) If p divides both (n!)i+1 and (n!)j+1, then the difference of those two numbers will also be divisible by p.

Hope that helps,

Alvaro

thank you Alvaro, I understand the first point, that if p divides (n!)+1, it must be greater than n, and the same is true for (n!)j+1, but why is p different in both cases, as the statement requires that the GCD((n!)i+1,(n!)j+1) = 1.

I have however problems with the second statement; (n!)j+1-((n!)i+1)=n!(j-i)=(n!)d. if p is prime and divides (n!)d it can not be greater than n, and can consequently not be the same p as above. We can thus say that (n!)i+1 and (n!)d are coprime and the same for (n!)j+1 and (n!)d. Does this implies that also (n!)i+1 and (n!)j+1 are also coprime. Anyway, we can produce two coprimes in this way.

thanks for your help, but I am not really at the complete understanding of the statement. I made a few numeric examples and it seems to fit, but is it always true ?

Wim

I think the point is, if p divides both x and y, then p divides mx+ny for any m and n. In particular, p divides x-y.

Nick

You're almost there... what you are doing is called proof by contradiction:

1. Initial assumption: two numbers are not coprime,
2. Then they must be divisible by a common prime number p.
3. From this, you derive two intermediate remarks or statements.
4. From the two statements, you arrive at a contradiction.
5. Hence the initial assumption is not correct.

Doe this help?

this is exactly the point Nick; a divisor of (n!)i+1 must be greater than n, as 2 can not divide a multiple of 2 +1, and the same is true for all the other numbers of n!.
a divisor of (n!)j+1, must also be greater than n, for the same reason. My problem is that I dont see why this divisor must be different and prime, so that we can conclude

GCD ((n!)i+1, (n!)j+1) =1

Let us take the difference of both numbers, we end with (n!)(j-i). Here we can say that any prime divisor of this number must be smaller or equal to n, for obvious reasons.

Thus we can say that for any prime divisor of the first number, it is greater than n, for any prime divisor of the second number it is smaller than n, thus they have no common divisor and

GCD ((n!)i+1, (n!)(j-i)) =1

in this way we have constructed two coprimes, and this is an element in the alternative proof for the infinite number of primes (alternative proof for the classical Euclid proof).

Such coprimes are for instance also the Fermat numbers. The rest of the proof can not be too difficult; suppose we have n, than (assuming the previous stuff is proven and understood), there is a prime divisor of n smaller than n, and a (co)prime number bigger than n. This way of reasoning indicates that there are infinite number of primes.

I hope I made the difficulties I have with the proof clear. thanks for your help anyway.

Wim

"My problem is that I dont see why this divisor must be different and prime, so that we can conclude

GCD ((n!)i+1, (n!)j+1) =1"

This seems obvious enough to me, and I think I might be able to make it obvious to you also. In your first message you stated that both i and j are less than n, or maybe even j can be equal to n, correct?

Since n > i and n >= j, then n! must be divisible by both i and j. In fact, we can multiply n! by whatever other positive integer we like, and that multiple of n! will still be divisible by both i and j. But if we add 1 to that n! or to that multiple of n!, we have completely thrown off this relationship. ((n!)i+1) = 1 mod i AND mod j AND mod n. Also, (n!)j+1) = 1 mod i AND mod j AND mod n.

indeed, so (n!)i+1 can be divisible by p, which is inevitably bigger than n. the same can be said of (n!)j+1, can be divisible by q. Or to put it more general, (n!)i+1 can be decomposed in a product of primes (or is a prime itself) and the same is true for (n!)j+1;

why is there no factor in the two products the same. All the p's and q's are bigger than n, there we agree I think.

The statement is in my opinion wrong and only valid in the hyptothesis that the number of primes is finite and n is the last prime.

anyway, thanks for your help

Pages

Subscribe to Comments for "topic entry on real numbers"