-5
\$\begingroup\$

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.

Calculate the number of perfect squares below a number \$n\$ where \$n\$ will be taken as an input


Examples:

There are 9 perfect squares below 100: 1, 4, 9, 16, 25, 36, 49, 64, 81

Constraints: \$0<n<10^6\$


Since this is a golfing challenge, the entry with least amount of bytes will win.

Best of Luck!

\$\endgroup\$
  • 8
    \$\begingroup\$ This is a trivial challenge, and all it does is generate results that show which language(s) are more "golfy". \$\endgroup\$ – Jeff Zeitlin Jul 13 '18 at 14:50
  • 3
    \$\begingroup\$ Let it be noted that although I agree this should be closed, I do not agree that this is a duplicate of the question cited. \$\endgroup\$ – Jeff Zeitlin Jul 13 '18 at 15:04
  • 4
    \$\begingroup\$ I disagree that this should be closed at all. While this challenge is uninteresting (note the votes), it has a clear specification and no direct duplicates; I disagree with the duplicate-vote because the main approach to a solution is different (modulo 1 or built-ins like is_square are irrelevant here, for example). Thus, I hammer-reopened the challenge. \$\endgroup\$ – JungHwan Min Jul 13 '18 at 15:17
  • 2
    \$\begingroup\$ @JeffZeitlin "If anyone feels that trivial challenges insult their intelligence, I encourage them to seek out languages that make the task less trivial." – Martin Ender # \$\endgroup\$ – user202729 Jul 13 '18 at 15:55
  • 7
    \$\begingroup\$ In conclusion: Being too easy is not a close reason. Please do not close a challenge just because it's too easy. Feel free to downvote however. \$\endgroup\$ – user202729 Jul 13 '18 at 15:56

15 Answers 15

1
\$\begingroup\$

Panacea, 3 bytes

<qc

Explanation:

<     decrement
 q    square root
  c   floor
\$\endgroup\$
5
\$\begingroup\$

brainfuck, 161 160 bytes

,>>>>>>+[-<<<<<+[>+>+>+<<<-]>[-<+>]>[>[>+<<<+>>-]>[<+>-]<<-]>[-]<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<[>>[-]>+<<<-]>>>[<<<+>>>-]<[>>+<<-]<<->-]<[-]>>>>]<<<<<-.

Try it online!

Finally, a challenge simple enough that I could attempt some brainfuckery.

Credits to https://esolangs.org/wiki/Brainfuck_algorithms for the squaring algorithm and the comparison algorithm ideas, Fatih Erikli's brainfuck visualizer, and to El Brainfuck for quick runs.

(Also to user202729 for noticing an unnecessary space in the code and for a link with a bash I/O wrapper.)

Calculates \$ i^2 \$ for each \$ i \$ starting from 1, and checks if \$ i^2 < n \$. Returns the last \$ i \$ for which that's true.

Input and output are usually ASCII characters representing numbers. For eg., in the TIO link, input d (ASCII 100) returns character tab \t (ASCII 9). Now links to a version that takes and returns numeric I/O directly. Assumes a wrapping implementation (for the comparison algorithm).

, n input
> i = 0
> isqr/temp0
> icopy1/ncopy/temp1
> icopy2/temp2
> temp3
> exitflag (is isqr lt n)
+[-                 while exitflag not 0
  <<<<<
  +                 increment i
  [>+>+>+<<<-]      make 3 copies of i (destructively)
  >[-<+>]           use one of them (temp0) to restore i

  Squaring by multiplying icopy1 with icopy2:
  >[                while icopy1 not 0
    >[>+<<<+>>-]    copy icopy2 to temp3 and add it to isqr
    >[<+>-]         restore icopy2 from temp3
    <<-             decrement icopy1
  ]
  >[-]              reset temp2 (icopy2) to 0

  Comparing n and isqr:
  <<<<[>>>+>+<<<<-] copy n to ncopy and temp2
  >>>>[<<<<+>>>>-]  restore n from temp2
  <[                while ncopy
    >+              increment temp2 as flag
    <<[>>[-]>+<<<-] if isqr gt 0 reset temp2 (destroys isqr & copies to temp3)
    >>>[<<<+>>>-]   restore isqr from temp3
    <[>>+<<-]       set exitflag to 1 if temp2 was not reset
    <<->-           decrement isqr & decrement ncopy 
    ]
  <[-]              reset isqr (would have been set to negative of n minus isqr)
  >>>>              check the flag and exit if isqr gt n
]
<<<<<-.              decrement i by 1 and output

!
\$\endgroup\$
3
\$\begingroup\$

brainfuck, 49 bytes

Use byte-value input/output. Can only process numbers up to maximum cell value. Requires a tape that has at least 3 cells to the left and 2 cells to the right of the initial memory pointer.

+>>,[<[<<]<[[<+>>+<-]++<[>+<-]<<+>]>>>->-]<<<<<-.

Try it online!

(with nice Bash wrapper that converts decimal input/output to byte input/output)


Based on the identity \$1 + 3 + 5 + \dots + (2n-1) = n^2\$     (so it subtracts 1, then 3, then 5, then 7, ... from the input \$n\$ until it is \$\le 0\$, then count number of subtraction)

Explanation:

# Mem layout: {r t A a c x}. Ptr initially at {a}.
# {t} == 0. r == result. a == 1, then increase to 3, 5, ...
# {c} counts from {a} to 0.
# {x} is the input, gradually decremented.

+        # a=1
>>,      # read x
[        # while x:
  <        # goto c
  [<<]<    # if c, goto {t}, else goto {a}
  [        # if not c:
    [<+>>+<-]    # A=c=a; a=0
    ++<[>+<-]    # a=2+A; A=0
    <<+>         # r+=1
  ]
  # now mem pointer is at {t} regardless of initial
  # value of {c}, and c!=0
  >>>-     # c-=1
  >-       # x-=1
]
<<<<<-.  # print r-1

Compilable Python code works the same way -- explanation in reverse.

\$\endgroup\$
3
\$\begingroup\$

Brain-Flak, 58 bytes

({()<([]){({}{(<({}[()])>)}{}[()])}{}({}((<><>)))>}<>[()])

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 3 bytes

’ƽ

Try it online!

Simply takes the floor of the square root of \$n-1\$. Assumes \$0\$ should be counted and assumes that we ought to find the number of perfect squares strictly lower than \$n\$. (This is just an illustration of why such trivial challenges are discouraged)

\$\endgroup\$
  • \$\begingroup\$ More or less. I'd not include 0, and floor instead of ceiling. \$\endgroup\$ – Jeff Zeitlin Jul 13 '18 at 15:02
  • \$\begingroup\$ Technically according to the phrasing of this question it would be incorrect as this would include n itself if it is a square while the question says less than n. \$\endgroup\$ – fəˈnɛtɪk Jul 13 '18 at 15:03
  • \$\begingroup\$ @JeffZeitlin You mean \$\lfloor\sqrt{n-1}\rfloor\$, no? \$\endgroup\$ – Mr. Xcoder Jul 13 '18 at 15:05
  • \$\begingroup\$ @Mr.Xcoder - Yes, actually. \$\endgroup\$ – Jeff Zeitlin Jul 13 '18 at 15:06
1
\$\begingroup\$

JavaScript, 25 bytes

f=n=>--n&&!(n**.5%1)+f(n)

Try it online

\$\endgroup\$
  • \$\begingroup\$ Not 100% sure about the spec but I think it should be f=n=>--n&&!(n**.5%1)+f(n). Now, n=>--n**.5|0 should work for 12 bytes. \$\endgroup\$ – Arnauld Jul 13 '18 at 16:01
  • \$\begingroup\$ Oh, right, it looks like 0 (wrongly) shouldn't be counted. Work away with that 12 byte version, was too rushed to figure out the Maths! ;) \$\endgroup\$ – Shaggy Jul 13 '18 at 16:03
1
\$\begingroup\$

Japt, 4 bytes

Port of Mr. XCoder Jelly Implementation

´U¬f

Try it online!

\$\endgroup\$
1
\$\begingroup\$

MATL - 4 bytes

Using the same approach as others

qX^k

Try it at MATL Online

Explanation

      Implicitly grab input
q     Subtract 1
X^    Compute the square root
k     Round down
      Implicitly display the result
\$\endgroup\$
  • \$\begingroup\$ Hey @suever! Working to get to 10k? :-) \$\endgroup\$ – Luis Mendo Jul 14 '18 at 16:53
  • \$\begingroup\$ @LuisMendo trying to get back into it a little :) \$\endgroup\$ – Suever Jul 14 '18 at 16:55
1
\$\begingroup\$

Brain-Flak, 76 bytes

{({}[()]<(({})){(<{}({}[({})({}[()])])>)}{}({}({})({}())[()])>)}{}{}({}[()])

Try it online!

Explanation

Uses a simple counting method. It has 3 counters, the number, the slice and the result. We decrement the number until it reaches zero, each time we do we also decrement the slice if it is non-zero. If the slice is zero we increment the result and set the slice to one less than twice the result.

This computes the square root via the sum of consecutive odds.

\$\endgroup\$
1
\$\begingroup\$

Dodos, 121 120 bytes

Also based on the identity \$1 + 3 + 5 + \dots + (2n-1) = n^2\$    . Thanks to H.PWiz for saving some bytes.

	dip f 1
f
	+ 1 > - A f F
F
	> - i r
	+ 1 1 >
i
	i I
I
	>
	>
r
	>
	> - A
A
	+ >
	+
-
	- dip
1
	
	dip + _
_
+
	dot
>
	dab

Try it online!

Fortunately there are no scroll bar in the code...


_       Returns an empty list.
1       Append 1.
-       Assume x<y, given (x, y) return (0, y-x).
> - A   Get the first element of a list (return 0 for empty list).
r       Reverse a list of 2 elements.
i       Incremential: Given (x, y) return (x, y) if x<y else (y, y).
f       Main function.

Writing Dodos code is similar to Haskell that all functions are (effectively) pure.

Bonus Haskell code (ungolfed) which this solution bases on.

\$\endgroup\$
  • \$\begingroup\$ 116 I think that is correct \$\endgroup\$ – H.PWiz Jul 20 '18 at 22:16
0
\$\begingroup\$

Neim, 7 bytes

𝐈Λq𝕚)𝐥<

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This does not answer the challenge as written. This returns the squares, not the count of them. \$\endgroup\$ – Jeff Zeitlin Jul 13 '18 at 15:54
  • \$\begingroup\$ @JeffZeitlin Fixed. \$\endgroup\$ – Okx Jul 13 '18 at 15:55
  • 1
    \$\begingroup\$ Better. Still doesn't answer the challenge, though; there are only 9 square below 100, not 10. \$\endgroup\$ – Jeff Zeitlin Jul 13 '18 at 15:57
0
\$\begingroup\$

JavaScript (Node.js), 14 12 bytes

-2 bytes by @Shaggy

_=>--_**.5|0

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 12 bytes: n=>--n**.5|0 \$\endgroup\$ – Shaggy Jul 13 '18 at 22:19
0
\$\begingroup\$

Noether, 9 bytes

I1-0.5^_P

Try it in the interpreter!

Explanation:

This is just an implementation of the formula \$\left\lfloor{\sqrt{n-1}}\right\rfloor\$:

I         - Push the user input onto the stack
 1        - Push 1 onto the stack
  -       - Pop two numbers a and b off the stack and push the result of a-b
   0.5    - Push 0.5 onto the stack
      ^   - Pop two numbers a and b off the stack and push the result of a^b
       _  - Pop the number on the top of stack, floor it and push the result
        P - Print the item on the top of the stack
\$\endgroup\$
0
\$\begingroup\$

Java 8, 22 bytes

n->(int)Math.sqrt(n-1)

Lambda using the formula \$\left\lfloor{\sqrt{n-1}}\right\rfloor\$. Trivial implementation. Try it online here.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 18 bytes

f(n){n=sqrt(n-1);}

Trivial implementation of the formula \$\left\lfloor{\sqrt{n-1}}\right\rfloor\$. Try it online here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.