BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Functions of Integers

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Junior | Next Rank: 30 Posts
Posts: 20
Joined: Mon Jul 27, 2009 7:13 am
Location: Chicago

Functions of Integers

by gmatgirl12 » Fri Oct 30, 2009 4:55 am
For every positive integer n, the function f(n)is defined to be the product of all even integers from 2 to n, inclusive. If p is the smallest prime factor h(100)+1. then p is:

A) between 2 and 10
B) between 10 and 20
c) between 20 and 30
D) between 30 and 40
e) greater than 40
Top
Source: — Problem Solving |
Senior | Next Rank: 100 Posts
Posts: 76
Joined: Sat Jan 24, 2009 3:00 pm
Thanked: 11 times
GMAT Score:730

by BuckeyeT » Fri Oct 30, 2009 7:08 am
If p is the smallest prime factor h(100)+1. then p is:
I'm going to assume your h(100) is actually f(100) or else, f(n) was supposed to be h(n).

I have some ideas to start the problem, but I cannot seem to figure it out.

f(100) = {2*4*...98*100}
This number will end in a "00" as the last number multiplied is 100.

f(100) + 1 = Some number ending in "01"
However, there are multiple possibilities for the ending three numbers 101, 201, 301... 901. And, some of these have least prime factors of 3 or 7. But, some seem to have significantly higher least primes.

Any additional thoughts?
Top
Master | Next Rank: 500 Posts
Posts: 177
Joined: Thu Aug 14, 2008 11:59 am
Thanked: 25 times

by mp2437 » Fri Oct 30, 2009 7:50 am
f(n) is same as h(n) here, just a typo.

Product of all even integers is 2*4*6*8*...*100, which is the same as 2^50(1*2*3*4*...*50), since you have 50 even integers. Thus, every integer up to 50 is divisible in this sequence.

HOWEVER, you have to add 1 to this result, which means that the next digit that will be able to divide this huge number will be greater than 50. Choice E.

To visualize it more simply, think of a smaller example, say h(10) = 2 * 4 * 6 * 8 * 10. This is the same as 2^5*(1*2*3*4*5) = 32 * 120 = 600. Note that you have 5 even integers in the original sequence (2,4,6,8,10), which is why you raise 2 to the 5th power. Now, add 1 to 600 to get 601. Note that there is no integer less than 5 that can divide into 601, which means that the next prime number that can divide 601 is larger than 5. Very similar to the example we have for h(100).

Hopefully this helps.
Top
Senior | Next Rank: 100 Posts
Posts: 76
Joined: Sat Jan 24, 2009 3:00 pm
Thanked: 11 times
GMAT Score:730

by BuckeyeT » Fri Oct 30, 2009 8:38 am
Thanks! Very clear explanation.
Top
Senior | Next Rank: 100 Posts
Posts: 70
Joined: Mon Oct 05, 2009 9:33 am

by chipbmk » Fri Oct 30, 2009 9:27 am
mp2437 wrote: To visualize it more simply, think of a smaller example, say h(10) = 2 * 4 * 6 * 8 * 10. This is the same as 2^5*(1*2*3*4*5) = 32 * 120 = 600.
Maybe I am wrong, maybe my calculator is broken, but 32 * 120 = 3840 NOT 600.

I am not sure if this changes any of your reasoning or the answer you would choose, but please let me know because I am slightly confused.

Also, this portion of your explanation is confusing to me, maybe someone can clarify?

"Product of all even integers is 2*4*6*8*...*100, which is the same as 2^50(1*2*3*4*...*50), since you have 50 even integers. Thus, every integer up to 50 is divisible in this sequence. "
Top
Master | Next Rank: 500 Posts
Posts: 177
Joined: Thu Aug 14, 2008 11:59 am
Thanked: 25 times

by mp2437 » Fri Oct 30, 2009 9:31 am
sorry, got ahead of myself and forgot to move the 0 (multiplying led me to 120 * 32 = 240 + 360 instead of 240 + 3600), my mistake. Same reasoning though. Using even smaller numbers will simplify even more so. :D

I found an even better explanation here:
https://www.urch.com/forums/gmat-math/11 ... xam-2.html

Particularly, this may be easier to understand:

"I will elaborate on this more to make it simple.

h(n) = 2 x 4 x .....n
h(100) = 2 x 4 x ...100

Since there are 50 even nos. in 1-100 we can write:
h(100) = 2^50 *(1x2x3x4...50)

now, h(100) will be divisible by each nos. from 1 to 50 as it is in the numerator.

but, h(100) + 1 = (2 x 4 x ...100 + 1) = 2^50 (1 x 2 x...50) +1

with 1 added to it these prime nos. cannot divide the nos. in simpler terms if A can divide B, A cannot divide B+1. say 2 can divide 10, but cannot divide 11.

Coming back to the problem, since h(100) is divisible by all prime nos. from 1-50, the no. which can divide h(100)+1 has to be greater than 50.

Hence, the answer is E"

Hope it helps.
Top
Senior | Next Rank: 100 Posts
Posts: 70
Joined: Mon Oct 05, 2009 9:33 am

by chipbmk » Fri Oct 30, 2009 9:48 am
mp2437 wrote: Particularly, this may be easier to understand:

"I will elaborate on this more to make it simple.

h(n) = 2 x 4 x .....n
h(100) = 2 x 4 x ...100

Since there are 50 even nos. in 1-100 we can write:
h(100) = 2^50 *(1x2x3x4...50)

now, h(100) will be divisible by each nos. from 1 to 50 as it is in the numerator.

but, h(100) + 1 = (2 x 4 x ...100 + 1) = 2^50 (1 x 2 x...50) +1

with 1 added to it these prime nos. cannot divide the nos. in simpler terms if A can divide B, A cannot divide B+1. say 2 can divide 10, but cannot divide 11.
This does make it more clear. Thanks for the explanation. Is that a rule or something that all even integers multiplied up to N equals what you wrote in this case 2^50(1x2x...50)? Are there other such rules, what if the question said it was all odd integers up to 100? or just all integers up to 100?

Thanks!
Top
Master | Next Rank: 500 Posts
Posts: 177
Joined: Thu Aug 14, 2008 11:59 am
Thanked: 25 times

by mp2437 » Fri Oct 30, 2009 11:01 am
For consecutive integers, say from 1 to 10, it is the same idea as that with just even integer products. The key here is that any number less than 100 will be divided by the product of 1 to 10, since the product contains a multiple of the number you are dividing it by (i.e - the product of 1 to 10 will be divisible by 7 because you have 1*2*3*...6*7*8*9*10, so dividing by 7 will work). This means that up to 10, you are certain that any number will be divisible in your product. However, if you try dividing by 11, you will see that nothing is divisible by it. So you know that adding 1 to this product, or any number for that matter, could make the number divisible by a prime number, but you have to keep in mind that the prime number will be greater than 10, since every prime number below it can already be divided into the main product.

Now for the example on even integers (same idea as the one above, only you distribute the 2 out)

For every even integer, they all share the "2" in common, so you could just pull it out and distribute accordingly. So the product of the 4 even integers 2 * 4 * 6 * 8 is the same (1*2) * (2*2) *(3*2) * (4*2), so you could pull out a 2 from each one, which could also be written as 1*2*3*4*2*2*2*2 = 2^4*(1*2*3*4). Naturally, you could see this being applied to any product of even integers up to n, where the product will be 2^n * (1*2*...*n), where n is the number of even integers in your set.
Top
Junior | Next Rank: 30 Posts
Posts: 20
Joined: Mon Jul 27, 2009 7:13 am
Location: Chicago

by gmatgirl12 » Fri Oct 30, 2009 4:09 pm
mp2437 wrote:For consecutive integers, say from 1 to 10, it is the same idea as that with just even integer products. The key here is that any number less than 100 will be divided by the product of 1 to 10, since the product contains a multiple of the number you are dividing it by (i.e - the product of 1 to 10 will be divisible by 7 because you have 1*2*3*...6*7*8*9*10, so dividing by 7 will work). This means that up to 10, you are certain that any number will be divisible in your product. However, if you try dividing by 11, you will see that nothing is divisible by it. So you know that adding 1 to this product, or any number for that matter, could make the number divisible by a prime number, but you have to keep in mind that the prime number will be greater than 10, since every prime number below it can already be divided into the main product.

Now for the example on even integers (same idea as the one above, only you distribute the 2 out)

For every even integer, they all share the "2" in common, so you could just pull it out and distribute accordingly. So the product of the 4 even integers 2 * 4 * 6 * 8 is the same (1*2) * (2*2) *(3*2) * (4*2), so you could pull out a 2 from each one, which could also be written as 1*2*3*4*2*2*2*2 = 2^4*(1*2*3*4). Naturally, you could see this being applied to any product of even integers up to n, where the product will be 2^n * (1*2*...*n), where n is the number of even integers in your set.
Thank you for the explanation! That makes a lot more sense now. The answer was E.
Top
Master | Next Rank: 500 Posts
Posts: 328
Joined: Thu Aug 07, 2008 5:25 pm
Location: Philadelphia
Thanked: 4 times
GMAT Score:550

by Abdulla » Sun Nov 01, 2009 12:04 am
My approach was different..

To find the Product of all even integers from 2 to n inclusive means finding the product of all integers from 2 to n inclusive that are multiple of 2.

= { ( Last term - First term ) / 2} +1 , so

f(n) = { (n-2) / 2 } + 1 , now we should find p which = f(100)+1

Using the above formula and plugin 100 for n

f(100) = { ( 100-2 ) / 2 } +1

f(100) = (98/2) +1

f(100) = 49 + 1 = 50

Since P= f(100) + 1 then,

p = 50 + 1 = 51 which is greater than 40 .. E is the answer.
Abdulla
Top
Post new topic Post Reply
• Page 1 of 1