Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What would Euler do?

  1. Apr 14, 2004 #1

    honestrosewater

    User Avatar
    Gold Member

    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
     
  2. jcsd
  3. Apr 15, 2004 #2

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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. sn:

    Code (Text):

    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, sn=n-[|n/10|]

    How's that?
     
  4. Apr 15, 2004 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    "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.
     
  5. Apr 15, 2004 #4

    honestrosewater

    User Avatar
    Gold Member

    Matt,
    Yes, but *I'm* not actually giving credit, whoever writes the history books is giving credit :wink: 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
     
    Last edited: Apr 15, 2004
  6. Apr 15, 2004 #5

    honestrosewater

    User Avatar
    Gold Member

    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
     
  7. Apr 15, 2004 #6

    honestrosewater

    User Avatar
    Gold Member

    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
     
  8. Apr 15, 2004 #7

    Njorl

    User Avatar
    Science Advisor

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

    Njorl
     
  9. Apr 15, 2004 #8

    honestrosewater

    User Avatar
    Gold Member

    :biggrin:

    Oh, that reminds me... wait I'll think of it...
     
  10. Apr 15, 2004 #9

    honestrosewater

    User Avatar
    Gold Member

    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
     
  11. Apr 15, 2004 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  12. Apr 15, 2004 #11

    honestrosewater

    User Avatar
    Gold Member


    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.
     
    Last edited: Apr 15, 2004
  13. Apr 15, 2004 #12

    honestrosewater

    User Avatar
    Gold Member

    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 :redface:
     
  14. Apr 15, 2004 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Finding the remainder is simple, repeatedly subtract ten until you obtain a number in the desired range.
     
  15. Apr 15, 2004 #14

    honestrosewater

    User Avatar
    Gold Member

    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
     
  16. Apr 15, 2004 #15

    honestrosewater

    User Avatar
    Gold Member

    Eureka! I think I might have it.

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

    Let me double-check.

    Rachel
     
    Last edited: Apr 15, 2004
  17. Apr 15, 2004 #16

    honestrosewater

    User Avatar
    Gold Member

    Nope. that's just n. duh
     
    Last edited: Apr 15, 2004
  18. Apr 15, 2004 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    this follows from a simple inductive argument.
     
  19. Apr 15, 2004 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  20. Apr 15, 2004 #19

    honestrosewater

    User Avatar
    Gold Member

    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
     
  21. Apr 15, 2004 #20

    honestrosewater

    User Avatar
    Gold Member

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?