A positive integer n is called sacred if it is divisible by all odd integers a for which n ≥ a 2 . Determine the sum of all sacred numbers.
As an arbitrary example, n = 1 5 is sacred because it is divisible by 1 and 3 .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Super-duper-cool :D Thanks..
Why did you use 7 only? @Jubayer Nirjhor ..
Log in to reply
Sorry I was editing the comment and somehow it got deleted. Here's the comment.
"If you're asking why I specially chose 7 to work with or how do I know in the first place that no a ≥ 7 works, actually I first set up the inequality and rearranged it. Then I noticed the a 2 ( a − 7 ) term and that if a ≥ 7 then the inequality doesn't hold. So we can rule out all a ≥ 7 ."
Nice. Bounding works better but this is nice to learn from :)
From the problem description, the set of factors of a sacred number n must be a superset of a set of the form S= {1, 3, 5, ... 2k-1}. Suppose it contains {1,3,5,7}. Then n >= 105. So S contains 9 too. But S contains {1,3,5,7,9} implies n>=315 so S contains {1,3,5,7,9,11,13,15,17}, and so on. In other words, S cannot contain 7. In other words, n < 49. Now brute force your way through the 48 possibilities to find that [1 .. 9, 12, 15, 18, 21, 24, 30, 45] are the only possibilities.
Nice straightforward solution!
Excellent. Elementary bounding is sometimes all that one needs to solve a problem. :D
If k 2 ≤ n < ( k + 2 ) 2 where k is an odd integer and n is sacred , then LCD ( 1 , 3 , . . . , k ) ∣ n , which implies that: ( k + 2 ) 2 > n > LCD ( 1 , 3 , . . . , k )
Observe that LCD ( 1 , 3 , . . . , k ) is larger than the product of the primes in that list, making the inequality into: ( k + 2 ) 2 > n > LCD ( 1 , 3 , . . . , k ) > (product of primes)
Observe that when k = 1 1 , the product of odd primes equal to or below 11 is 1 1 5 5 , which is larger than 1 3 2 , which sets the upper boundary of sacred number to 121.
When 1 2 ≤ n < 3 2 , the LCD is 1 and the sacred numbers are 1 to 8, with a sum of 36.
When 3 2 ≤ n < 5 2 , the LCD is 3 and the sacred numbers are 9,12,15,18,21, and 24, with a sum of 99.
When 5 2 ≤ n < 7 2 , the LCD is 15 and the sacred numbers are 30 and 45, with a sum of 45.
There is no sacred numbers beyond 7 2 .
Therefore the required value is 3 6 + 9 9 + 4 5 = 2 1 0 .
(Is it a coincidence that the points awarded for this question is 210?)
Nice Solution.... :D It's obvio a co-incidence!!
Log in to reply
Wonderful problem. Amazed by the number-theoretic approaches. But bounding works the best :D
Problem Loading...
Note Loading...
Set Loading...
Consider max { odd a : a 2 < n } . For a ≥ 7 , n must be divisible by all of a , a − 2 , a − 4 . Notice that g cd ( a , a − 2 ) = g cd ( a − 2 , a − 4 ) = g cd ( a , a − 4 ) = 1 so a ( a − 2 ) ( a − 4 ) ∣ n . Now clearly n ≤ ( a + 2 ) 2 . So we have a ( a − 2 ) ( a − 4 ) ≤ n ≤ ( a + 2 ) 2 ⟹ 4 ( a − 1 ) + a 2 ( a − 7 ) ≤ 0 which is clearly not true for a ≥ 7 . Hence a ∈ { 1 , 3 , 5 } .
If a = 1 then 1 ≤ n ≤ 9 so n ∈ { 1 , 2 , ⋯ , 9 } .
If a = 3 then 9 ≤ n ≤ 2 5 and 3 ∣ n so n ∈ { 9 , 1 2 , ⋯ , 2 4 } .
If a = 5 then 2 5 ≤ n ≤ 4 9 and 1 5 ∣ n so n ∈ { 3 0 , 4 5 } .
The solution set is { 1 , 2 , ⋯ , 8 , 9 } ∪ { 9 , 1 2 , ⋯ , 2 4 } ∪ { 3 0 , 4 5 } .
The sum is 2 1 0 .