Remarkable numbers

[Thales12345]

GIVEN: A strictly positive natural number n is "remarkable" if any strictly positive natural number less than or equal to n can be written as the sum of different divisors of n.
(Examples:
1 is remarkable
->1 = 1
2 is remarkable
->1 = 1
->2 = 2
4 is remarkable
->1 = 1
->2 = 2
->3 = 1 + 2
->4 = 4
6 is remarkable
->1 = 1
->2 = 2
->3 = 3
->4 = 1 + 3
->5 = 2 + 3
->6 = 6)

TO PROVE: 6^100 is remarkable

As I write out the sequence of numbers further, I quickly notice that every multiple of 6 belongs to the sequence. Is this sufficient as 'proof'?

 

[JeffM]

No it is not a proof.

You have shown that 6 * 1 is remarkable. Therefore, there is a set of positive integers such that the product of 6 and a member of the set is "remarkable." Let k be a member of the set. Now prove that k + 1 is a member of the set

 

[Thales12345]

No it is not a proof.

You have shown that 6 * 1 is remarkable. Therefore, there is a set of positive integers such that the product of 6 and a member of the set is "remarkable." Let k be a member of the set. Now prove that k + 1 is a member of the set

I don't understand this very well. By 'member of the set' do you mean a number from the sequence of remarkable numbers?
If so, how do you prove that k + 1 is a member of the set when you have no numbers?

Or do you mean by 'member of the set' a divisor of a remarkable number?

 

[JeffM]

You want to prove that every multiple of 6 is remarkable. All those can be expressed as 6n, a product of 6 and some integer.

You have proved that 6 = 6 * 1 is remarkable. Therefore there exists a NON-EMPTY set of positive integers such that each integer in the set when multiplied by 6 is remarkable. Right?

Let k be an arbitrary member of that set. So k is an integer [imath]\ge[/imath] 1 and 6k is remarkable.

Thus it is obvious that k + 1 is a positive integer. If you can show that 6(k + 1) is remarkable, then k + 1 is also a member of that set. Thus the set is the set of all positive integers. 1 is in it. So 1 + 1 = 2 is in it. Thus, 2 + 1 = 3 is in it. And so on forever.

It is called a proof by weak mathematical induction.

 

[Thales12345]

Okay, I see what you mean.
But, how do you show that 6(k+1) is remarkable?
We don't know what 'value' 6(k+1) has and the divisors are just 1, 2, 3, 6, k+1 , 2(k+1), 3(k+1) and 6(k+ 1).
Can we also just check here for all strictly positive natural numbers =<6(k+1) ?

 

[lev888]

Okay, I see what you mean.
But, how do you show that 6(k+1) is remarkable?
We don't know what 'value' 6(k+1) has and the divisors are just 1, 2, 3, 6, k+1 , 2(k+1), 3(k+1) and 6(k+ 1).
Can we also just check here for all strictly positive natural numbers =<6(k+1) ?

In your proof that 6(k+1) is remarkable you can use the assumption that 6k is remarkable. Are you familiar with proofs by induction?

 

[Thales12345]

In your proof that 6(k+1) is remarkable you can use the assumption that 6k is remarkable. Are you familiar with proofs by induction?

No not at all. I do understand JeffM's setup and what you can achieve with it, but I don't see how you can prove that a number is remarkable without knowing its divisors (without variables in it).

 

[lev888]

By the way, it may be true that all multiples of 6 are remarkable, but this is a more general statement than what the problem is asking to prove (which is 6^100). So maybe first try to prove that if 6^k is a remarkable number, than 6^(k+1) is also remarkable.

 

[Thales12345]

By the way, it may be true that all multiples of 6 are remarkable, but this is a more general statement than what the problem is asking to prove (which is 6^100). So maybe first try to prove that if 6^k is a remarkable number, than 6^(k+1) is also remarkable.

Can you explain to me how I can show that a number with a variable (so 6^k) is remarkable?

 

[JeffM]

Actually, you are correct. We do not need to do a proof by induction. It is simpler than that.

[math]\text {Let } n \text { be any positive integer.}[/math]
[math]\text {Let } m \text { be any positive integer } \le 6n.[/math]
[math]\exists \text { integers } p \text { and } q \text { such that } 0 \le p \le 6,[/math]
[math]0 \le q \le 5, \text { and } m = pn + q.[/math]
[math]\text {Divisors of } 6n \text { include } 1,\ 2,\ 3,\ 6,\ n,\ 2n,\ 3n, \text {and } 6n.[/math]
[math]p = 1 \implies pn = n \implies m = n + q.[/math]
[math]p = 2 \implies pn = 2n \implies 2n + q.[/math]
[math]p = 3 \implies pn = 3n \implies m = 3n + q.[/math]
[math]p = 4 \implies pn = n + 3n \implies m = n + 3n + q.[/math]
[math]p = 5 \implies pn = 2n + 3n \implies m = 2n + 3n + q.[/math]
[math]p = 6 \implies pn = 6n \implies m = 6n.[/math]
[math]p = 0 \implies pn = 0 \implies m = q.[/math]
If q is zero, then m is the sum of divisors of n.

So the whole thing reduces to showing that q is the sum of divisors of n if q > 0.

[math]q = 1 \implies q \text { is a divisor of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 2 \implies q \text { is a divisor of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 3 \implies q \text { is a divisor of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 4 \implies q = 1 + 3, \text { divisors of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 5 \implies q = 2 + 3, \text { divisors of } n \implies m \text { a sum of divisors.}[/math]
No matter what, m can be expressed as the sum of divisors of 6n.

But m is any positive integer less than or equal to 6n. So 6n is remarkable.

EDIT: This is kind of a clunky proof. Probably lev or someone can dream up a more elegant one. But it is just an elaboration of your demonstration that 6 itself is remarkable.

 

[lev888]

Actually, you are correct. We do not need to do a proof by induction. It is simpler than that.

[math]\text {Let } n \text { be any positive integer.}[/math]
[math]\text {Let } m \text { be any positive integer } \le 6n.[/math]
[math]\exists \text { integers } p \text { and } q \text { such that } 0 \le p \le 6,[/math]
[math]0 \le q \le 5, \text { and } m = pn + q.[/math]
[math]\text {Divisors of } 6n \text { include } 1,\ 2,\ 3,\ 6,\ n,\ 2n,\ 3n, \text {and } 6n.[/math]
[math]p = 1 \implies pn = n \implies m = n + q.[/math]
[math]p = 2 \implies pn = 2n \implies 2n + q.[/math]
[math]p = 3 \implies pn = 3n \implies m = 3n + q.[/math]
[math]p = 4 \implies pn = n + 3n \implies m = n + 3n + q.[/math]
[math]p = 5 \implies pn = 2n + 3n \implies m = 2n + 3n + q.[/math]
[math]p = 6 \implies pn = 6n \implies m = 6n.[/math]
[math]p = 0 \implies pn = 0 \implies m = q.[/math]
If q is zero, then m is the sum of divisors of n.

So the whole thing reduces to showing that q is the sum of divisors of n if q > 0.

[math]q = 1 \implies q \text { is a divisor of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 2 \implies q \text { is a divisor of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 3 \implies q \text { is a divisor of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 4 \implies q = 1 + 3, \text { divisors of } n \implies m \text { a sum of divisors.}[/math]
[math]q = 5 \implies q = 2 + 3, \text { divisors of } n \implies m \text { a sum of divisors.}[/math]
No matter what, m can be expressed as the sum of divisors of 6n.

But m is any positive integer less than or equal to 6n. So 6n is remarkable.

EDIT: This is kind of a clunky proof. Probably lev or someone can dream up a more elegant one. But it is just an elaboration of your demonstration that 6 itself is remarkable.

We need to take into account the requirement that divisors are different. This can be done by stating that n>1 (n=1 is already handled in OP), then we know that 6n divisors you mentioned are all different. Other than that looks good.

 

[JeffM]

We need to take into account the requirement that divisors are different. This can be done by stating that n>1 (n=1 is already handled in OP), then we know that 6n divisors you mentioned are all different. Other than that looks good.

@lev888 If we are not doing a proof by induction, I am missing your point. (Not disagreeing necessarily; just not understanding.)

 

[lev888]

@lev888 If we are not doing a proof by induction, I am missing your point. (Not disagreeing necessarily; just not understanding.)

"A strictly positive natural number n is "remarkable" if any strictly positive natural number less than or equal to n can be written as the sum of different divisors of n"
Therefore, when considering m=pn+q we need to make sure that pn and q sums use different divisors.

 

[JeffM]

@lev888

You are completely correct: my so-called proof is invalid. It has to be invalid because the conjecture is false.

Consider 102 = 6 * 17 = 2 * 3 * 17. Clearly, 102 is a multiple of 6.

Its factors are 1, 2, 3, 6, 17, 34, 51, and 102.

Consider the number 16.

16 < 17 < 34 < 51 < 102. So no multiple of 17 can be a term in a sum of positive numbers equalling 16.

1 + 2 + 3 + 6 = 12 < 16.

Thus no sum of the factors of 6 can possibly equal 16.

Therefore, it is false that every multiple of 6 is a remarkable number.; 102 is counter-example.

In fact, every multiple of 6 and a prime greater than 13 is not a remarkable number.

 

[lev888]

@lev888

You are completely correct: my so-called proof is invalid. It has to be invalid because the conjecture is false.

Consider 102 = 6 * 17 = 2 * 3 * 17. Clearly, 102 is a multiple of 6.

Its factors are 1, 2, 3, 6, 17, 34, 51, and 102.

Consider the number 16.

16 < 17 < 34 < 51 < 102. So no multiple of 17 can be a term in a sum of positive numbers equalling 16.

1 + 2 + 3 + 6 = 12 < 16.

Thus no sum of the factors of 6 can possibly equal 16.

Therefore, it is false that every multiple of 6 is a remarkable number.; 102 is counter-example.

In fact, every multiple of 6 and a prime greater than 13 is not a remarkable number.

Can't accept the credit - I didn't think your proof was invalid, I thought it needed a small correction to account for that requirement.