Multiply by thee is hard

If σ 0 ( n ) = 8 \sigma_0(n) = 8 , find sum of all possible values of a a satisfying a = σ 0 ( 3 n ) a = \sigma_0(3n) .

Notation : σ 0 ( n ) \sigma_0 (n) denote the number of positive factors of the integer n n (inclusive of 1 and itself).


The answer is 47.

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.

2 solutions

Otto Bretscher
Apr 23, 2016

If n = 3 m q n=3^mq where 3 ∤ q 3\not | q , then σ 0 ( n ) = σ 0 ( 3 m ) σ 0 ( q ) = ( m + 1 ) σ 0 ( q ) = 8 \sigma_0(n)=\sigma_0(3^m)\sigma_0(q)=(m+1)\sigma_0(q)=8 , so that m + 1 m+1 can be 1,2,4 or 8. Now σ 0 ( 3 n ) = σ 0 ( 3 m + 1 ) σ 0 ( q ) = 8 ( m + 2 ) m + 1 \sigma_0(3n)=\sigma_0(3^{m+1})\sigma_0(q)=\frac{8(m+2)}{m+1} , which can be 16, 12, 10, or 9. The answer is 47 \boxed{47}

finally a three-liner!

Joel Yip - 5 years, 1 month ago

Log in to reply

I'm still working on it...it's a two-liner now ;) I usually write a rough draft first, save it (to make sure it's not lost if I get interrupted), and then I try to streamline it.

The problem is so though that I have no chance to get it down to one line while showing all my work.

Otto Bretscher - 5 years, 1 month ago
Joel Yip
Apr 22, 2016

If σ 0 ( n ) = 8 \displaystyle { \sigma }_{ 0 }\left( n \right) =8 ,

then it has to be expressed as p 1 p 2 p 3 \displaystyle { p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 } , p 1 3 p 2 \displaystyle { p }_{ 1 }^{ 3 }{ p }_{ 2 } or p 1 7 \displaystyle { p }_{ 1 }^{ 7 } .

Scenario 1: n = p 1 p 2 p 3 \displaystyle n = { p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }

Case 1: p 1 = 3 { p }_{ 1 }=3

Since n = p 1 p 2 p 3 \displaystyle n = { p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }

So 3 n = 3 p 1 p 2 p 3 = p 1 2 p 2 p 3 3 × 2 × 2 = 12 f a c t o r s \displaystyle 3n=3{ p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }\\ ={ p }_{ 1 }^{ 2 }{ p }_{ 2 }{ p }_{ 3 }\Longrightarrow 3\times 2\times 2=12\quad factors

Case 2: p 2 = 3 { p }_{ 2 }=3

Since n = p 1 p 2 p 3 \displaystyle n = { p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }

So 3 n = 3 p 1 p 2 p 3 = p 2 2 p 1 p 3 3 × 2 × 2 = 12 f a c t o r s \displaystyle 3n=3{ p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }\\ ={ p }_{ 2 }^{ 2 }{ p }_{ 1 }{ p }_{ 3 }\Longrightarrow 3\times 2\times 2=12\quad factors

Case 3: p 3 = 3 { p }_{ 3 }=3

Since n = p 1 p 2 p 3 \displaystyle n = { p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }

So 3 n = 3 p 1 p 2 p 3 = p 3 2 p 1 p 2 3 × 2 × 2 = 12 f a c t o r s \displaystyle 3n=3{ p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }\\ ={ p }_{ 3 }^{ 2 }{ p }_{ 1 }{ p }_{ 2 }\Longrightarrow 3\times 2\times 2=12\quad factors

Case 4: p 1 , 2 , 3 3 { p }_{ 1,2,3 }\neq 3

Since n = p 1 p 2 p 3 \displaystyle n = { p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 }

So 3 n = 3 p 1 p 2 p 3 2 × 2 × 2 × 2 = 16 f a c t o r s \displaystyle 3n=3{ p }_{ 1 }{ p }_{ 2 }{ p }_{ 3 } \Longrightarrow 2\times 2\times 2\times 2=16\quad factors

Scenario 2: n = p 1 3 p 2 \displaystyle n= { p }_{ 1 }^{ 3 }{ p }_{ 2 }

Case 1: p 1 = 3 { p }_{ 1 }=3

Since n = p 1 3 p 2 \displaystyle n= { p }_{ 1 }^{ 3 }{ p }_{ 2 }

So 3 n = 3 p 1 3 p 2 = p 1 4 p 2 5 × 2 = 10 f a c t o r s \displaystyle 3n={ 3p }_{ 1 }^{ 3 }{ p }_{ 2 }\\ ={ p }_{ 1 }^{ 4 }{ p }_{ 2 } \Longrightarrow 5\times 2=10\quad factors

Case 2: p 2 = 3 { p }_{ 2 }=3

Since n = p 1 3 p 2 \displaystyle n= { p }_{ 1 }^{ 3 }{ p }_{ 2 }

So 3 n = 3 p 1 3 p 2 = p 1 3 p 1 2 4 × 3 = 12 f a c t o r s \displaystyle 3n={ 3p }_{ 1 }^{ 3 }{ p }_{ 2 }\\ ={ p }_{ 1 }^{ 3 }{ p }_{ 1 }^{ 2 } \Longrightarrow 4\times 3=12\quad factors

Case 3: p 1 , 2 3 { p }_{ 1,2 } \neq 3

Since n = p 1 3 p 2 \displaystyle n= { p }_{ 1 }^{ 3 }{ p }_{ 2 }

3 n = 3 p 1 3 p 2 2 × 4 × 2 = 16 f a c t o r s \displaystyle 3n={ 3p }_{ 1 }^{ 3 }{ p }_{ 2 }\Longrightarrow 2\times 4\times 2=16\quad factors

Scenario 3: n = p 1 7 \displaystyle n= { p }_{ 1 }^{ 7 }

Case 1: p 1 = 3 { p }_{ 1 }=3

Since n = p 1 7 \displaystyle n= { p }_{ 1 }^{ 7 }

3 n = 3 p 1 7 = p 1 8 9 f a c t o r s \displaystyle 3n=3{ p }_{ 1 }^{ 7 }\\ ={ p }_{ 1 }^{ 8 }\Longrightarrow 9\quad factors

Case 2: p 1 3 { p }_{ 1 } \neq 3

Since n = p 1 7 \displaystyle n= { p }_{ 1 }^{ 7 }

3 n = 3 p 1 7 = 3 p 1 7 8 × 2 = 16 f a c t o r s \displaystyle 3n=3{ p }_{ 1 }^{ 7 }\\ ={ 3p }_{ 1 }^{ 7 }\Longrightarrow 8\times 2=16\quad factors

That's all the cases so 12 + 16 + 10 + 9 = 47 12+16+10+9=\boxed { 47 }

Moderator note:

As you realized, the main consideration is the largest power of 3 that divides n n , which determines the value of σ ( 3 n ) \sigma(3n) .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...