My answer is changing with the same code

Question

I am a complete python beginner and I am trying to solve this problem :

A number is called triangular if it is the sum of the first n positive integers for some n For example, 10 is triangular because 10 = 1+2+3+4 and 21 is triangular because 21 = 1+2+3+4+5+6. Write a Python program to find the smallest 6-digit triangular number. Enter it as your answer below.

I have written this program:

n = 0
trinum = 0
while len(str(trinum)) < 6:
    trinum = n*(n+1)/2
    n += 1
print(trinum)

And it only works in the python I have installed on my computer if I say while len(str(trinum)) < 8: but it is supposed to be while len(str(trinum)) < 6:. So I went to http://www.skulpt.org/ and ran my code there and it gave me the right answer with while len(str(trinum)) < 6: like it's supposed to. But it doesn't work with 6 with the python i have installed on my computer. Does anyone have any idea what's going on?

Incidentally, converting numbers to strings is usually a Bad Idea. Better to do something like `trinum < 1e6`. — Kevin, Apr 17 '15 at 19:35
@Kevin: It's probably better to use `1000000` instead of introducing floats and having to convince yourself that there's no possibility of a rounding error affecting you here… — abarnert, Apr 17 '15 at 19:35
@abarnert: Yeah, but then you have the problem of needing to count the zeros... At least Perl lets you stick underscores in as digit separators. — Kevin, Apr 17 '15 at 19:37
In terms of "better," I'd go for `any(sum(range(n)) == number for n in range(number))`. — TigerhawkT3, Apr 17 '15 at 19:39
The number of digits in a given integer x in base n is `1 + floor(log(x, n))`. Is there a case where rounding errors can cause that formula to fail? — kojiro, Apr 17 '15 at 19:40
@Kevin: Well then, `10**6`, which is still an int in Python. — abarnert, Apr 17 '15 at 19:42
@kojiro: The real question isn't that, but can you reasonably expect a novice to convince himself that the answer to that is no? If not, you're better off not telling him to use floats. — abarnert, Apr 17 '15 at 19:42
@abarnert sadly programmers have to be experts in the problem domain they're coding in. If that problem domain is math… — kojiro, Apr 17 '15 at 19:44
@kojiro: Most mathematicians are not experts in floating point issues. And they often don't have to be, unless you teach them to use floating point when they don't need it… — abarnert, Apr 17 '15 at 19:51
As a side note, Skulpt is not a complete or fully-compliant Python implementation. It's not even sure which Python 2.x version it's implementing. So, while it's a very cool project, using it to figure out what Python is "supposed to do" is generally not a good idea. — abarnert, Apr 17 '15 at 19:55
@abarnert most of the mathematician programmers I know are acutely aware of floating point issues. But I could have a sample bias. — kojiro, Apr 17 '15 at 19:57
@kojiro: Well, yeah, I suppose most mathematicians aren't programmers, and most mathematicians who _are_ programmers are either doing something close to mathematical physics or other numerical-realm stuff, or coding Haskell, so you're probably right. :) — abarnert, Apr 17 '15 at 20:27
@MalikBrahimi: Using recursion instead of a loop would (a) not solve his problem, and (b) actually break his code if n>1000. So, that's a pretty good reason for him not to use it. — abarnert, Apr 17 '15 at 20:28
Something that would make sense (and which I suspect @MalikBrahimi was aluding to with his suggestion of recursion), is to simply update `trinum` by adding `n` to it, rather than recomputing the whole sum on each iteration. This conveniently sidesteps the division issue. — Blckknght, Apr 17 '15 at 20:32
@Blckknght Yes, but there must be a way to avoid the maximum recursion depth. — Malik Brahimi, Apr 17 '15 at 20:33
I was assuming a similar `while` loop to the question's code. Perhaps `while trinum < 10**5: n+=1; trinum += n` to avoid the string issues as well as the division issue. — Blckknght, Apr 17 '15 at 20:39
@Blckknght: Sure, but that has nothing to do with using recursion; you can do the naive algorithm iteratively or recursively, and you can do the less naive algorithm iteratively or recursively… — abarnert, Apr 17 '15 at 20:46
@abarnert: Yes, I agree. I was just guessing that Malik's suggestion of recursion was primarily motivated by wanting to suggest having each successive triangular number calculated from the previous one (as you'd do in a recursive algorithm, usually). Perhaps I was reading more into his suggestion than was warranted. — Blckknght, Apr 17 '15 at 20:51
I dunno; I think this problem can be solved [by formula](http://www.wolframalpha.com/input/?i=1+%2B+floor%28log10%28n+*+%28n+%2B+1%29+%2F+2%29%29+%3D+6%3B+solve+for+n). — kojiro, Apr 17 '15 at 21:01
@kojiro: Wouldn't solving it analytically require `floor` to be invertible? — abarnert, Apr 17 '15 at 21:14
@abarnert the problem is a min of an inequality. I think to solve it analytically you still have to use `min` and guarantee a positive root. I'm reasonably sure it can be done, but I'm going to cop out on an actual proof. — kojiro, Apr 17 '15 at 21:22
@kojiro: OK, I'll take your word for it that there's a good chance it's doable but it's not worth your time to do. :) — abarnert, Apr 17 '15 at 21:53
@abarnert: To be fair, when using floats with integer values, there are no rounding errors. — Dolda2000, Apr 18 '15 at 02:47
@Dolda2000: Really? So you think `1e30 - 1 == 1e30` is a bug in Python, not something inherent to floating point? — abarnert, Apr 20 '15 at 03:28
@abarnert: Well, sure, "integer values in range of the mantissa's precision", if you necessarily want me to qualify that statement. Point being that `1e6` is well within that precision, as is every other 53-bit integer. :) — Dolda2000, Apr 20 '15 at 03:35
@Dolda2000: Sure, anyone who already knows how to deal with floating point issues understands the 53-bit range for IEEE doubles. But my point is that a novice who's writing code like this probably doesn't. He could just guess and cross his fingers, or search for some statement that he can take on faith without understanding it, or learn enough that he understands… or he can just not use floats where he has no need to use floats. — abarnert, Apr 20 '15 at 04:23

Bill Lynch · Answer 1 · 2015-05-13T14:08:10.140

30

Short Answer

In Python 3, division is always floating point division. So on the first pass you get something like str(trinum) == '0.5'. Which isn't what you want.

You're looking for integer division. The operator for that is //.

Long Answer

The division operator changed in Python 2.x to 3.x. Previously, the type of the result was dependent on the arguments. So 1/2 does integer division, but 1./2 does floating point division.

To clean this up, a new operator was introduced: //. This operator will always do integer division.

So in Python 3.x, this expression (4 * 5)/2 is equal to 10.0. Note that this number is less than 100, but it has 4 characters in it.

If instead, we did (4*5)//2, we would get the integer 10 back. Which would allow your condition to hold true.

edited May 13 '15 at 14:08

answered Apr 17 '15 at 19:34

Bill Lynch

80,138
16
128
173

4

I don't know if the OP will get that this is what leads to the problem without more explanation: eventually he's got, say, `1035.0`, which is not under 6 characters long, even though it's under 6 digits. – abarnert Apr 17 '15 at 19:36
1

It should be noted that to get Python 2.2 and up to do floating point division for the normal operator (consistent with 3), you can use `from __future__ import division`. This will allow the OP to get the same (and incorrect) behavior between the two different interpreters. – jpmc26 Apr 18 '15 at 06:14
2

Note: `//` is **not** a new operator. It's been there since [python **2.2**](https://docs.python.org/2/whatsnew/2.2.html#pep-238-changing-the-division-operator). So, if you don't really really have to run a python version that was released more than 13/14 years ago just use `//` *any* time you want integer divisor and add the `__future__` import as suggested by `jpmc26`. – Bakuriu Apr 18 '15 at 11:01

TigerhawkT3 · Answer 2 · 2015-04-17T20:33:15.480

9

In Python 2, the / operator performs integer division when possible: "x divided by y is a remainder b," throwing away the "b" (use the % operator to find "b"). In Python 3, the / operator always performs float division: "x divided by y is a.fgh." Get integer division in Python 3 with the // operator.

edited Apr 17 '15 at 20:33

answered Apr 17 '15 at 19:34

TigerhawkT3

48,464
6
60
97

2

Your "if necessary" comment is mostly incorrect. In Python 3, `x/y` is never going to be an `int`, even if the result is integral. `4/2` is `2.0`, not `2`. In Python 2, your phrasing is also a bit misleading, as `/` only does integer division if both numbers are `int`s. If one is a float, you'll get the same result as you do in Python 3. – Blckknght Apr 17 '15 at 20:30
Thanks; I'll tidy that up. – TigerhawkT3 Apr 17 '15 at 20:32

score 8 · Answer 3 · answered Apr 17 '15 at 19:41

You have two problems here, that combine to give you the wrong answer.

The first problem is that you're using /, which means integer division in Python 2 (and the almost-Python language that Skulpt implements), but float division in Python 3. So, when you run it on your local machine with Python 3, you're going to get floating point numbers.

The second problem is that you're not checking for "under 6 digits" you're checking for "under 6 characters long". For positive integers, those are the same thing, but for floats, say, 1035.5 is only 4 digits, but it's 6 characters. So you exit early.

If you solve either problem, it will work, at least most of the time. But you really should solve both.

So:

n = 0
trinum = 0
while trinum < 10**6: # note comparing numbers, not string length
    trinum = n*(n+1)//2 # note // instead of /
    n += 1
print(trinum)

The first problem is fixed by using //, which always means integer division, instead of /, which means different things in different Python versions.

The second problem is fixed by comparing the number as a number to 10**6 (that is, 10 to the 6th power, which means 1 with 6 zeros, or 1000000) instead of comparing its length as a string to 6.

score 4 · Answer 4 · edited May 23 '17 at 10:29

Taking Malik Brahimi's answer further:

from itertools import *
print(next(dropwhile(lambda n: n <= 99999, accumulate(count(1))))

count(1) is all the numbers from 1 to infinity.
accumulate(count(1)) is all the running totals of those numbers.
dropwhile(…) is skipping the initial running totals until we reach 100000, then all the rest of them.
next(…) is the next one after the ones we skipped.

Of course you could argue that a 1-liner that takes 4 lines to describe to a novice isn't as good as a 4-liner that doesn't need any explanation. :)

(Also, the dropwhile is a bit ugly. Most uses of it in Python are. In a language like Haskell, where you can write that predicate with operator sectioning instead of a lambda, like (<= 99999), it's a different story.)

score 3 · Answer 5 · answered Apr 17 '15 at 20:19

3

The division method in Py2.x and 3.x is different - so that is probably why you had issues. Just another suggestion - which doesn't deal with divisions and lengths - so less buggy in general. Plus addition is addition anywhere.

trinum = 0
idx =0

while trinum < 99999: #largest 5 digit number
    idx += 1
    trinum += idx

print trinum

answered Apr 17 '15 at 20:19

Rcynic

392
3
10

1

"addition is addition everywhere"—except in many languages, where it's actually addition modulo `INT_MAX` (or, in C, where it's undefined for signed numbers if it may possibly overflow). :) But yeah, I get the point. – abarnert Apr 17 '15 at 20:59

Malik Brahimi · Answer 6 · 2015-04-17T21:10:42.617

2

import itertools # to get the count function
n, c = 0, itertools.count(1) # start at zero 

while n <= 99999:
    n = n + next(c)

edited Apr 17 '15 at 21:10

answered Apr 17 '15 at 20:40

Malik Brahimi

16,341
7
39
70

If you're going to go iterator-style, why not use `for n in count(1):` instead of a `while` loop with explicit incrementing? – abarnert Apr 17 '15 at 21:02
Is `itertools.count` just a *infinite* generator like the one I have made? – Malik Brahimi Apr 17 '15 at 21:03
Exactly; `count(i=0)` counts from `i` to infinity. – abarnert Apr 17 '15 at 21:06
Actually, everything you're doing here is a simple itertools function, not just that. See [here](http://stackoverflow.com/a/29709367/908494). I'm pretty sure I've crossed the horizon where more conciseness doesn't mean more clarity at some point there. :) – abarnert Apr 17 '15 at 21:09
I think your code is about as novice-friendly a demonstration of the "accumulate as you go along" idea as you're going to get. (The `accumulate` from my version may be OK, but the `dropwhile` is probably not…) – abarnert Apr 17 '15 at 21:12
Yes I understood that much but what exactly is `dropwhile` – Malik Brahimi Apr 17 '15 at 21:13
See [the docs](https://docs.python.org/3/library/itertools.html#itertools.dropwhile). It means to keep dropping elements while the predicate (`lambda n: n <= 99999`, in my case) is true. – abarnert Apr 17 '15 at 21:16

My answer is changing with the same code

6 Answers6

Short Answer

Long Answer

Linked