Creating a Sequence Without Gauss: The Euler Challenge

[honestrosewater]

I think this will be my new mantra ;) but it is actually related to the question.
I want to define the sequence (s_n) where n is natural and whose nth term, t_n, is the sum of the digits of n.
I want to do this without using Gauss's modular arithmetic. This may be one of those 'easier said than done' problems. But I find it hard to believe that everyone (ex. Euler) was completely stumped by it before Gauss came along.

At the moment, I'm thinking that factorials may play a part. Besides the more obvious reasons why, the fact that 0! = 1 might help with the equivalence between 0 and 9 that must eventually be handled.

Anyway, just thought I'd see if anyone has anything to add.

Happy thoughts

Rachel

 

[quantumdude]

Hi Rachel,

I'm not familiar with this problem, or with Euler's solution, but one way to do this without modular arithmetic is to use the greatest integer function. Consider the following table for n vs. s_n:

n              s[sub]n[/sub]
--------    ---------------
0-9          n        =n-9*0
10-19        n-9      =n-9*1
20-29        n-18    =n-9*2
30-39        n-27    =n-9*3
.
.
.
m0-m9       n-9*m  (m is any whole number)

Now for any number in the "n" column, m=[|n/10|], where
f(x)=[|x|] is the greatest integer function.

So, s_n=n-[|n/10|]

How's that?

 

[matt grime]

"Gauss's Modulo arithmetic"? I think you're miscrediting slightly there; modulo arithemetic has been around for thousands of years, even if we didn't formally call it that, and people might well have noticed any patters that arise and done induction arguments on them.

 

[honestrosewater]

Matt,
Yes, but *I'm* not actually giving credit, whoever writes the history books is giving credit All of my sources credit Gauss, and, even when they don't explicitly say so, it is tacitly understood that the person credited was the first to formalize the subject, or give a complete treatment of it, or otherwise be known to have said enough about it in the right kind of way. Historians aren't mind-readers, sans dreaming.

Tom,
First, to clarify- I didn't mean to imply that Euler *had* solved it, I don't know whether he did or didn't. I was just wondering how he- or anyone else before Gauss- might have solved it.

Yes, your thoughts mirror mine, and mine yours, exactly, we both even used "m" :)
BUT how do you translate the *concept* of the greatest integer (a.k.a floor) function into the language of arithmetic (I am confining myself to arithmetic and conventional sequence/series terminology)? I have just done some quick research on this function and it is everywhere described in words. Cut-the-knot.org even says, "The floor function [x] furnishes an example of a function that couldn't be defined by a simple formula...". This is disheartening, but...

I remember thinking about subtracting the "fractional" or "rational" part, and I don't remember why I gave up on this idea... so I will go be stubborn and try it again.

Toodahloo

Rachel

 

[honestrosewater]

Looking at my notes/scribbles ;)

I remember (fondly) reading (at least part of) the book "An Introduction to the Theory of Computation", by Michael Sipser. I don't have the book anymore and don't remember all of the terminology used, so please bear with me.

(You may be able to do this in a simpler way, ex. using one machine, but the following should suffice for now)

You can construct 9 finite automaton, S_1, S_2, ...S_9, each having the following in common:

10 states = {Q0, Q1, Q2, Q3, Q4, Q5, Q6, Q8, Q9}
alphabet = {1}
start state = Q0

but differing in their accept states. S_1 having accept state = Q1, and, in general,
S_a having accept state = Qa. (Q0 is never an accept state)

Now comes the part that I don't remember, so I will make a diagram with arrows ->. There is only one letter in the alphabet, each time it is read, traverse the arrow. (remember to start on Q0)

->Q0->Q1->Q2->Q3->Q4->Q5->Q6->Q7->Q8->Q9---
-------^
(Q9 loops back to Q1.)

Again, my apologies if that wasn't fun.

Now, you can convert each natural number n to an equivalent string of 1's by finding the partial sum at n of the series 10^(t-1), t = {1, 2, 3, etc.}

Next, feed this string of 1's into each of your machines, S_1, S_2, etc. The one that accepts it (the one that is in its accept state after reading the complete string) tells you the sum of the digits of your original n; the sum is equal to the a in S_a, the machine with accept state Qa.
Ex.
1 converts to 1, which S_1 accepts.
14 converts to 11111111111111, which S_5 accepts.

If anyone knows how I can say all of this using arithmetic, please share :)

Happy thoughts

Rachel

 

[honestrosewater]

Or...

I would of course be happy with the related proof that the sums of the digits of all multiples of 9 equal 9. I cannot see how to prove this yet either.

Oh well, back to work :)

Rachel

 

[Njorl]

I thought this would be a thread about adopting a lazy lifestyle. After all, Euler was famous for his minimization methods.

Njorl

 

[honestrosewater]

I thought this would be a thread about adopting a lazy lifestyle. After all, Euler was famous for his minimization methods.

Njorl

Oh, that reminds me... wait I'll think of it...

 

[honestrosewater]

Oh, yeah-

What does an astronaut sing in space?

"I can't get no rarefaction"

Hardee har har... made that up myself. Of course it isn't technically true, but...

Happy thoughts

Rachel

 

[matt grime]

to define [x/10] where x is an integer using only basic arithmetic it suffices to do:

let r be the remainder after divison by 10 (simple operation inside Z), then [x/10] = (x-r)/10

 

[honestrosewater]

to define [x/10] where x is an integer using only basic arithmetic it suffices to do:

let r be the remainder after divison by 10 (simple operation inside Z), then [x/10] = (x-r)/10

I don't understand. Can you define "remainder after division by 10"?

The closest thing, as far as I can see, (and I may be wrong) to what you are suggesting is

[n - (n/10)]/10

which doesn't work.

The way I see it, n - 9*[(n/10) - (digit in ones place/10)]

Which is obvious if you realize that dividing by ten = moving the decimal one place to the left ;)

But then you have to translate "digit in ones place"... if you can figure out how to subtract all the digits in the tens place and up... it sounds like the answer will involve exponents since what you subtract from n depends on/varies with the value of n...

Happy thoughts

Rachel

P.S. Matt, I want to do it this way as an excerise. I want to know if it can be done. If it can be done, I want to know how, and if it can't be done, I want to know why (and by why I really mean how). This is how I gain an understanding (vs. just memorizing facts). This reminds me of a Feynman anecdote about names of birds... if you've read it, it's the same idea.

 

[honestrosewater]

Addendum

Sorry, my reasoning about exponents may not have been clear.
I'm not sure how to explain it exaclty, but ask yourself, When does a derivative contain a variable?
Perhaps that doesn't help, sorry

 

[matt grime]

Finding the remainder is simple, repeatedly subtract ten until you obtain a number in the desired range.

 

[honestrosewater]

Matt,
Thank you. I see what you mean, but I have to say, "subtract 10 this many times." and define "this many" for all n, in general. I suppose I could say for n in such and such range, a>n>b, I guess this would be partitioning N. I'm not familiar with partitions and am not sure if I can use them, considering the restraints I have put on myself.
If you are familiar with partitions, and can explain them briefly, I am usually a quick study.

Rachel

 

[honestrosewater]

Eureka! I think I might have it.

n - 9*( [11*n/10] - [n/10])

Let me double-check.

Rachel

 

[honestrosewater]

Nope. that's just n. duh

 

[matt grime]

I would of course be happy with the related proof that the sums of the digits of all multiples of 9 equal 9. I cannot see how to prove this yet either.

Oh well, back to work :)

Rachel

this follows from a simple inductive argument.

 

[matt grime]

Number theory: let n and p be any two integers (positive say) then there exist a well defined pair q and r with 0<=r<p and n=pq+r

 

[honestrosewater]

Number theory: let n and p be any two integers (positive say) then there exist a well defined pair q and r with 0<=r<p and n=pq+r

Matt,
Let me see if I understand. Keeping your definitions,
if p=1, then r=0, and it reduces to
for all n in N, there exists some q in Z such that n=q.
I was tempted to say that this follows because N is a subset of Z, but that is not enough. It follows from the definition of Z: a is in Z if a is in N, -(a) is in N, or a=0.
Is this correct so far? Sorry if this seems like a step backward, but I haven't ever had to prove this before (self-study, remember ;) I will try one more case, before attempting to generalize...

if p=2, then 0<=r<2, r={0,1}
n=2q+0
n=2q+1
Now I notice that it's not clear if you mean for q and r to be integers also, as I have assumed.
Rachel

 

[honestrosewater]

Matt,
I see that you aren't online, so I will proceed with caution. Assuming q and r are in Z

if p=2, then r={0,1}
n=2q+0
or
n=2q+1

r=0 when n is even.
r=1 when n is odd.

I see this will take more time than I expected, so I'll say tahtah for now...

Rachel

 

[honestrosewater]

Matt,
When you say inductive argument, you mean that the proof will involve induction? You use that term intentionally?
Rachel

 

[matt grime]

I'm ont sure if you're still doing this or not.

The fundamental property of N/Z that we want is that it is ordere, after we subtract p from n we get e number strictly less than n, we stop at the last positive one.

 

[Gokul43201]

multiples of 9

Like Matt said,

It's easy to show inductively that sigma[9*k] = 9, using the additive property of the sigma function, i.e.: sigma[a+b] = sigma[a] + sigma.

So, assuming sigma[9*k] = 9,

sigma[9*(k+1)] = sigma[9*k + 9] = sigma[18] = 9

 

[honestrosewater]

Okay, wow, that *was* simple ;) Now I forget why I wanted to know! hehehe... sorry, I just woke up. Oh yes, it is a step in another proof. I will post the proof as soon as I make some coffee and type it out.
Thanks to everyone for your help!
Rachel