Summing 1 + 11 + 111 + … and My Problem Solving Technique.

September 17, 2011

This post was inspired by a question on the comment second of my last post about the prime-ness of 111…111.  The question is: what’s the sum of 1 + 11 + 111 + … + 111…111?  This seemed kind of silly to me (especially if the sum has less than 10 terms) but I quickly realized that I couldn’t figure out a "closed form" without appealing to weird "carry" tricks.  So I tried to figure something else out. 

Because my final solution to this question was somewhat unsatisfying, I’ve made this a special kind of post!  This post will have two main purposes: to try to answer this question and to show what kinds of things I do when I don’t know the answer to a problem.  So let’s begin.

 

First, I scribbled out lots of examples to see if there were patterns in the numbers.  Indeed, there are, but there was no nice way to describe them in general without creating a whole lot of variables and expanding the number of terms out into a base-ten sum.  This was frustrating.  Especially because I knew there might be an easy answer looming out there that I wasn’t clever enough to see. 

Second, I noted that 11 and 111 and 1111 are kind of weird numbers; written in base 10 they look pretty, but they don’t have much else in common.  As we saw in the last post, a few are prime but many are not, and many have very strange prime factorizations — these factorizations do group together, but that seemed to be too far away from this problem to use.  So, maybe another base would make them better formed?  I plugged away in wolfram alpha.  The first two bases I tried were base 2 and base 11.  Neither one worked nicely.  When I tried base 5, I found that the numbers followed an interesting pattern:

1, 11, 111, 1111, 11111, 111111, \dots

were mapped to

1, 21, 421, 13421, 323421, 12023421, \dots

Note that the last few digital always stay the same here.  Because the decimal form of these numbers is 1 + 10 + 100 + 10000 + … this is not all that surprising.  We’re essentially adding the base-5 versions of these together.  Note that 400_{5} means the number 400 in base 5; in decimal this is the number 100.  So 400_{5} = 100_{10}.  We drop the _{10} in our base 10 numbers and note the following:

1 = 1_{5}

10 = 20_{5}

100 = 400_{5}

1000 = 13000_{5}

10000 = 310000_{5}

100000 = 11200000_{5}

and while this seems to have a bit of a pattern, it grows too fast to be of use for adding.  On the other hand, I found that base 5 can be fairly neat when you input numbers that have "nice forms" in base 10.  Try it out!

 

Third, I was a bit upset, so I went back to thinking that I could write the number of terms as n = a_{0} + a_{1}10 + a_{2}10^{2} + \dots + a_{k}10^{k} and some some mods to figure out the digits.  The first digit will be easy: it’s just a_{0}.  But then what’s the carry?  After a bit, I worked out that it will just be \frac{n - a_{0}}{10}.  This did not seem to be going anywhere, since this number might be somewhat large too; we would need to add this number n - 1 times, and then there’s another carry that will look significantly more complex than the one I just wrote.  After trying this for five carries, I started to lose track of what I was doing; the formula was getting much more difficult than just doing "normal" addition.  This clearly wasn’t going to go anywhere.  At this point, a flash of insight hit me.  Of course.  This is just like adding 1 + 10 + 100 + 1000 + …, but only a little bit off.  But how much off? 

 

Fourth, I thought that, okay, 1 + 11 + 111 + 1111 +… is the same sum as 1 + 10 + 100 + 1000 + … with a difference of exactly 1 + 11 + 111 + … with one less term.  If there are n terms in the original, then it is equal to 1 + 10 + 100 + 1000 + \dots with n terms plus 1 + 11 + 111 + \dots with n -1 terms.  Note, then, that if we define the term ONE_{k} to be the sum of k terms that look like 1 + 11 + 111 + 1111\dots, then we have ONE_{k} = 111\dots 111 + ONE_{k-1}.  At this point, I began kicking myself, because this tells me nothing new about the problem; in fact, it is essentially a restatement of the problem!  But because of this, I thought about what happens when we do addition in 10’s.  I realized that it is exactly the same sort of thing we are doing when we add 11’s, but each successive digit will raise by 1.  So for example, while

1 + 10 + 100 + 1000 + 10000 = 11111

we have

1 + 11 + 111 + 1111 + 11111 = 12345

 

Each digit, starting at the left, is one plus the one before it.  Of course, this suggests a pattern.  But then what happens when you get far enough along? 

 

1 + 11 + 111 + 11111 + \dots + 111111111111 = 123456790122

 

which does not look as pretty.  But look; if we add in the following way, this becomes easy!  (I’ve attempted to use a chart to display place values.)

 

1 2 3 4 5 6 7 8 9      
                1 0    
                  1 1  
                    1 2
+                      
1 2 3 4 5 6 7 9 0 1 1 2

 

Which is exactly what we got above!  Note here that I’ve made a "10" that sits inside the tenth decimal place (and so is implicitly a carry of 1 in the ninth place) and a "11" that sits in the tenth place (and so is a carry of 1 in the tenth place and 1 in the eleventh place) and so on.  I’ve found that this method of computing is slightly faster than computing the original sum by hand and much less space consuming.  Unfortunately, the clever (and even not-so-clever) reader will notice that this is still the sum of n - 8 terms.  Though I find it faster because you are only adding at most three things in each column (carries included).  I tried to speed-test myself by adding together 20 terms this way and by doing 1 + 11 + 111 + … etc. straight out.  My times are as follows:

 

Original Way (Adding 1 + 11 + 111…): 1 minute. 

New Way (Described above): 40 seconds.

 

I also was much less confident doing this the original way (try it; you’ll have to keep track of the carry and the number of ones you need to add up and that gets confusing).  The most time consuming part about the "new way" was writing out the problem; I did not count this in the "original way" because it’s just as easy to visualize the problem as it is to write it out — it would take significantly longer.  If I were to only time the "calculation" part, the new way took me about 15 seconds.  Pretty good for a human.

 

But, this solution was the best I could do.  I do not have a closed form.  If anyone has a different or more interesting solution, let me know.  I didn’t want to resort to asking google, but maybe there’s a cute trick that makes this into a nice closed form.  I’m not sure.

 

Edit: Of course, there is an easier solution which was provided to me by Josh "The Widowmaker" Silverman over at his blog.  The key was to represent this as a geometric series (something that I seem to have completely missed out on).  It turns out that the closed form expression is

\frac{1}{81}(10^{n+1} - 10 - 9n)

for the sum of the first n numbers of this form.  To see the derivation, go to his blog and read it over.

Advertisements

9 Responses to “Summing 1 + 11 + 111 + … and My Problem Solving Technique.”

  1. astri said

    I’m still confuse… can you tell me in indonesian, please…

    • Kayla Andrea S. Caliba said

      Menyimpulkan 1 + 11 + 111 + … dan Teknik Pemecahan Masalah saya.
      September 17, 2011
      Posting ini terinspirasi oleh pertanyaan pada komentar kedua tulisan terakhir saya tentang-prime an dari 111 … 111. Pertanyaannya adalah: apa jumlah 1 + 11 + 111 + … + 111 … 111? Semacam ini tampak konyol bagi saya (terutama jika jumlah itu memiliki kurang dari 10 hal) tapi aku cepat menyadari bahwa saya tidak bisa mencari “bentuk tertutup” tanpa memanfaatkan trik aneh “membawa”. Jadi saya mencoba untuk mencari sesuatu yang lain keluar.

      Karena solusi akhir saya untuk pertanyaan ini agak tidak memuaskan, saya telah membuat jenis khusus dari posting! Posting ini akan memiliki dua tujuan utama: untuk mencoba menjawab pertanyaan ini dan untuk menunjukkan apa jenis hal yang saya lakukan ketika saya tidak tahu jawaban untuk masalah. Jadi mari kita mulai.

      Pertama, saya menulis keluar banyak contoh untuk melihat apakah ada pola dalam angka. Memang ada, tapi tidak ada cara yang baik untuk menjelaskan secara umum tanpa membuat seluruh banyak variabel dan memperluas jumlah istilah keluar ke sejumlah basis-sepuluh. Ini adalah frustasi. Terutama karena saya tahu mungkin ada jawaban yang mudah menjulang di luar sana bahwa saya tidak cukup pintar untuk melihat.

      Kedua, saya mencatat bahwa 11 dan 111 dan 1111 adalah jenis nomor aneh; ditulis dalam basis 10 mereka terlihat cantik, tapi mereka tidak memiliki banyak lagi kesamaan. Sebagaimana kita lihat di pos terakhir, sedikit yang prima tetapi banyak yang tidak, dan banyak memiliki faktorisasi prima yang sangat aneh – ini melakukan faktorisasi kelompok bersama-sama, tapi itu tampaknya terlalu jauh dari masalah ini untuk digunakan. Jadi, mungkin dasar lain akan membuat mereka lebih baik terbentuk? Saya terpasang jauh di wolfram alpha. Dua yang pertama basis saya mencoba adalah basis 2 dan basis 11. Tak satu pun bekerja dengan baik. Ketika saya mencoba basis 5, saya menemukan bahwa angka-angka diikuti pola yang menarik:

      dipetakan ke

      Perhatikan bahwa digital belakangan selalu tetap sama di sini. Karena bentuk desimal dari angka-angka ini adalah 1 + 10 + 100 + 10000 + … ini tidak semua yang mengejutkan. Kami pada dasarnya menambahkan dasar-5 versi bersama ini. Catatan itu berarti jumlah 400 dalam basis 5; dalam desimal ini adalah nomor 100. Jadi. Kami turun di 10 nomor basis kami dan perhatikan hal berikut:

      dan sementara ini tampaknya memiliki sedikit pola, tumbuh terlalu cepat untuk digunakan untuk menambahkan. Di sisi lain, saya menemukan bahwa dasar 5 dapat cukup rapi ketika Anda nomor input yang memiliki “bentuk yang bagus” dalam basis 10. Coba saja!

      Ketiga, aku agak kesal, jadi saya kembali berpikir bahwa saya bisa menulis jumlah istilah sebagai dan beberapa beberapa mods untuk mengetahui digit. Angka pertama akan mudah: hanya saja. Tetapi kemudian apa artinya saldo? Setelah sedikit, saya bekerja bahwa itu hanya akan. Ini tampaknya tidak akan ke mana-mana, karena jumlah ini mungkin agak besar juga, kita perlu menambahkan ini kali jumlah, dan kemudian ada carry lain yang akan terlihat secara signifikan lebih kompleks daripada yang saya baru saja menulis. Setelah mencoba ini selama lima karies, saya mulai kehilangan jejak dari apa yang saya lakukan, rumus semakin jauh lebih sulit daripada hanya melakukan “normal” Selain itu. Ini jelas tidak akan pergi ke mana pun. Pada titik ini, kilatan wawasan memukul saya. Tentu saja. Ini hanya seperti menambahkan 1 + 10 + 100 + 1000 + …, tetapi hanya sedikit off. Tapi berapa banyak dari?

      Keempat, saya berpikir bahwa, oke, 1 + 11 + 111 + 1111 + … adalah jumlah yang sama dengan 1 + 10 + 100 + 1000 + … dengan perbedaan tepat 1 + 11 + 111 + … dengan satu istilah kurang. Jika ada istilah-istilah dalam bahasa aslinya, maka sama dengan dengan istilah ditambah dengan istilah. Catatan, bahwa jika kita mendefinisikan istilah tersebut sebagai penjumlahan istilah yang mirip, maka kita harus. Pada titik ini, saya mulai menendang diriku sendiri, karena ini memberitahu saya sesuatu yang baru tentang masalah ini, bahkan, pada dasarnya pernyataan ulang dari masalah! Tapi karena ini, saya berpikir tentang apa yang terjadi ketika kita melakukan penambahan 10 itu. Saya menyadari bahwa itu adalah persis jenis yang sama hal yang kita lakukan ketika kita menambahkan 11, tetapi setiap digit berturut-turut akan meningkatkan dengan 1. Jadi misalnya, sementara

      1 + 10 + 100 + 1000 + 10000 = 11111

      kita harus

      1 + 11 + 111 + 1111 + 11111 = 12345

      Setiap digit, mulai dari sebelah kiri, adalah satu ditambah satu sebelumnya. Tentu saja, hal ini menunjukkan pola. Tapi kemudian apa yang terjadi ketika Anda mendapatkan cukup jauh bersama?

      yang tidak terlihat cantik. Tapi lihat, jika kita tambahkan dengan cara berikut, ini menjadi mudah! (Saya sudah mencoba menggunakan grafik untuk menampilkan nilai tempat.)

      1 2 3 4 5 6 7 8 9
      1 0
      1 1
      1 2
      +
      1 2 3 4 5 6 7 9 0 1 1 2

      Dan itulah yang kita punya di atas! Catatan di sini bahwa saya telah membuat “10” yang duduk di dalam tempat desimal kesepuluh (dan begitu juga secara implisit carry dari 1 di tempat kesembilan) dan “11” yang duduk di tempat kesepuluh (dan sebagainya adalah carry dari 1 di tempat kesepuluh dan 1 di tempat kesebelas) dan sebagainya. Saya telah menemukan bahwa metode komputasi adalah sedikit lebih cepat daripada menghitung jumlah asli dengan tangan dan memakan ruang lebih sedikit. Sayangnya, (dan bahkan yang tidak terlalu pintar) pintar pembaca akan melihat bahwa ini masih merupakan jumlah dari istilah. Meskipun saya merasa lebih cepat karena Anda hanya menambahkan paling banyak tiga hal dalam setiap kolom (membawa termasuk). Aku mencoba untuk mempercepat menguji diri dengan menambahkan bersama 20 hal cara ini dan dengan melakukan 1 + 11 + 111 + … dll langsung. Kali saya adalah sebagai berikut:

      Asli Way (Menambahkan 1 + 11 + 111 …): 1 menit.

      Cara Baru (Dijelaskan di atas): 40 detik.

      Saya juga jauh kurang percaya diri melakukan ini dengan cara yang asli (mencobanya, Anda harus melacak Saldo dan jumlah yang Anda perlu menambahkan dan yang akan membingungkan). Bagian yang paling memakan waktu tentang “cara baru” telah menuliskan masalah, saya tidak menghitung ini dalam “cara yang asli” karena itu hanya sebagai mudah untuk memvisualisasikan masalah seperti itu adalah untuk menulis itu – itu akan mengambil secara signifikan lebih lama . Jika saya waktu hanya “perhitungan” bagian, cara baru butuh waktu sekitar 15 detik. Cukup bagus untuk manusia.

      Namun, solusi ini adalah yang terbaik yang bisa lakukan. Saya tidak memiliki bentuk tertutup. Jika ada yang memiliki solusi yang berbeda atau lebih menarik, beritahu saya. Saya tidak ingin resor untuk meminta google, tapi mungkin ada trik lucu yang membuat ini menjadi sebuah bentuk tertutup bagus. Saya tidak yakin.

      Edit: Tentu saja, ada solusi mudah yang diberikan kepada saya oleh Josh “peti mati” Silverman atas di blognya. Kuncinya adalah untuk mewakili ini sebagai rangkaian geometris (sesuatu yang saya tampaknya telah sepenuhnya terjawab di). Ternyata ungkapan bentuk tertutup adalah

      untuk jumlah dari angka pertama dari formulir ini. Untuk melihat derivasi, pergi ke blog dan membacanya.
      Bago! I-click ang mga salita sa itaas upang i-edit at tumingin ng mga kahaliling translation. Huwag pansinin
      Google Translate para sa Negosyo:Toolkit ng TagapagsalinTranslator ng WebsiteGlobal Market Finder

  2. Anonymous said

    The pattern is 123456790 repeated to 81 places then becomes 123455790123446 if your largest number has 96 ones……..

  3. Gary said

    The pattern is 123456790 repeated to 81 places then becomes 123455790123446 if your largest number has 96 ones……..

    A big question is why the sum has no 8’s???

  4. Anonymous said

    grt wrk dude…

  5. Lao Tsu [quote] “Superstitiousness is ignorance and should be avoided.” Try doing something with this stuff.—>The consumer based petro chemical nuclear Industrial age we all now live in? Calamity for humanity with Carcinogenic toxic radio active pollution. Or this: THE New World Order iLLUMINATi fREEMASONRY Global Cabal. The major religions have a common “meme” thread if you will. THE Jews await their “messiah” The Bible [catholic or protestant] has the apocalypse or Armagedeon where there will be The Anti Christ false prophet or beast. The Moslems have The Dajjal or Al Aawar Al dajjal. The Tibetan buddhists have Maitreya. THE New World Order iLLUMINATi fREEMASONRY Global Cabal, most likely eagerly await this entity as well? Hint nudge wink secret handshake secret password secret question. [yada yada yada] kING james chrsitian love is a farce in Northern Ireland for the catholics HELLO? Lao Tsu [quote] “Superstitiousness is ignorance and should be avoided.” In regards to supernatural or esoteric beliefs. The History of Cultures and religions. The “CULT” phenomenom?

  6. Jayne said

    Pretty great post. I simply stumbled upon your blog and wanted to say that I’ve really loved
    browsing your blog posts. After all I will be subscribing to your feed and I hope you
    write once more very soon!

  7. For latest news you have to pay a quick visit world wide web
    and on the web I found this website as a most
    excellent web site for hottest updates.

  8. Hi to every body, it’s my first pay a visit of
    this weblog; this weblog includes amazing and truly fine stuff designed for
    visitors.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: