title: Find max sequence length

text:
# Question
Title: Find max sequence length
Assume we have a string, and we want to find the maximum repeated sequence of every letter.

For example, given the sample input:

```
"acbaabbbaaaaacc"

```

Output for the sample input can be:

```
a=5
c=2
b=3

```

Rules:

* Your code can be function or a program - for you to choose
* Input can be by stdin, file or function parameter
* The output should contain only characters that appear in the input
* Input max length is 1024
* The output order does not matter, but it has to be printed in the form \[char\]=\[maximum repeated sequence\]\[delimiter\]
* The string can contain any character

The competition ends on Thursday 3rd at 23:59 UTC.

# Answer
> 22 votes
# 8086 machine code, 82 80

Contents of the `x.com` file:

```
B7 3D 89 DF B1 80 F3 AA 0D 0A 24 B4 01 CD 21 42
38 D8 74 F7 38 17 77 02 88 17 88 C3 31 D2 3C 0D
75 E9 BF 21 3D B1 5E 31 C0 F3 AE E3 EE 4F BB 04
01 8A 05 D4 0A 86 E0 0D 30 30 89 47 02 3C 30 77
04 88 67 03 43 89 3F 89 DA B4 09 CD 21 47 EB D7

```

It only supports repetitions of up to 99 characters.

Source code (served as input for the `debug.com` assembler), with comments!

```
a
    mov bh, 3d         ; storage of 128 bytes at address 3d00
    mov di, bx
    mov cl, 80
    rep stosb          ; zero the array
    db 0d 0a 24
; 10b
    mov ah, 1
    int 21             ; input a char
    inc dx             ; calculate the run length
    cmp al, bl         ; is it a repeated character?
    je  10b
    cmp [bx], dl       ; is the new run length greater than previous?
    ja  11a
    mov [bx], dl       ; store the new run length
; 11a
    mov bl, al         ; remember current repeating character
    xor dx, dx         ; initialize run length to 0
    cmp al, d          ; end of input?
    jne 10b            ; no - repeat
    mov di, 3d21       ; start printing run lengths with char 21
    mov cl, 5e         ; num of iterations = num of printable characters
; 127
    xor ax, ax
    repe scasb         ; look for a nonzero run length
    jcxz 11b           ; no nonzero length - exit
    dec di
    mov bx, 104        ; address of output string
    mov al, [di]       ; read the run length
    aam                ; convert to decimal
    xchg al, ah
    or  ax, 3030
    mov [bx+2], ax
    cmp al, 30         ; was it less than 10?
    ja  145
    mov [bx+3], ah     ; output only one digit
    inc bx             ; adjust for shorter string
; 145
    mov [bx], di       ; store "x=" into output string
    mov dx, bx         ; print it
    mov ah, 9
    int 21
    inc di
    jmp 127            ; repeat
; 150

rcx 50
n my.com
w
q

```

Here are some golfing techniques used here that I think were fun:

* array's address is `3d00`, where `3d` is the ascii-code for `=`. This way, the address for array's entry for character `x` is `3d78`. When interpreted as a 2-character string, it's `x=`.
* Output buffer is at address `104`; it overwrites initialization code that is no longer needed. End-of-line sequence `0D 0A 24` is executed as harmless code.
* The `aam` instruction here doesn't provide any golfing, though it could...
* Writing the number twice, first assuming it's greater than 10, and then correcting if it's smaller.
* Exit instruction is at an obscure address `11b`, which contains the needed machine code `C3` by luck.

# Answer
> 14 votes
# CJam, ~~27~~ ~~26~~ 25 bytes

```
l:S_&{'=L{2$+_S\#)}g,(N}/

```

Try it online.

### Example

```
$ cjam maxseq.cjam <<< "acbaabbbaaaaacc"
a=5
c=2
b=3

```

### How it works

```
l:S       " Read one line from STDIN and store the result in “S”.                   ";
_&        " Intersect the string with itself to remove duplicate characters.        ";
{         " For each unique character “C” in “S”:                                   ";
  '=L     " Push '=' and ''.                                                        ";
  {       "                                                                         ";
    2$+_  " Append “C” and duplicate.                                               ";
    S\#)  " Get the index of the modified string in “S” and increment it.           ";
  }g      " If the result is positive, there is a match; repeat the loop.           ";
  ,       " Retrieve the length of the string.                                      ";
  (       " Decrement to obtain the highest value that did result in a match.       ";
  N       " Push a linefeed.                                                        ";
}/        "                                                                         ";

```

# Answer
> 9 votes
## J - 52 bytes

Well, a simple approach again.

```
f=:([,'=',m=:":@<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1~~.

```

Explanation:

```
f=:([,'=',m=:":@<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1~~.
                                                 ~~. Create a set of the input and apply it as the left argument to the following.
   ([,'=',m=:":@<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1    The function that does the work
                                             "0 1    Apply every element from the left argument (letters) with the whole right argument (text).
                                  @.(+./@E.)         Check if the left string is in right string.
                       (]m~[,{.@[)                   If yes, add one letter to the left string and recurse.
             ":@<:@#@[                               If not, return (length of the left string - 1), stringified.
    [,'=',                                           Append it to the letter + '='

```

Example:

```
   f 'acbaabbbaaaaacc'
a=5
c=2
b=3
   f 'aaaabaa'
a=4
b=1

```

If free-form output is allowed (as in many other answers), I have a **45 bytes** version too. These boxes represent a list of boxes (yes, they're printed like that, although SE's line-height breaks them).

```
   f=:([;m=:<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1~~.
   f 'acbaabbbaaaaacc'
┌─┬─┐
│a│5│
├─┼─┤
│c│2│
├─┼─┤
│b│3│
└─┴─┘
   f 'aaaabaabba'
┌─┬─┐
│a│4│
├─┼─┤
│b│2│
└─┴─┘

```

# Answer
> 8 votes
# Ruby, 72

```
(a=$*[0]).chars.uniq.map{|b|puts [b,a.scan(/#{b}+/).map(&:size).max]*?=}

```

This takes input from command line arguments and outputs to stdout.

# Answer
> 7 votes
# GolfScript, 26 bytes

```
:s.&{61{2$=}s%1,/$-1=,n+}%

```

Try it online.

Explanation:

* `:s` saves the input string in the variable `s` for later use.
* `.&` extracts the unique characters in the input, which the rest of the code in the `{ }%` loop then iterates over.
* `61` pushes the number 61 (ASCII code for an equals sign) on top of the current character on the stack, to act as an output delimiter.
* `{2$=}s%` takes the string `s` and replaces its characters with a 1 if they equal the current character being iterated over, or 0 if they don't. (It also leaves the current character on the stack for output.)
* `1,/` takes this string of ones and zeros, and splits it at zeros.
* `$` sorts the resulting substrings, `-1=` extracts the last substring (which, since they all consist of repetitions of the same character, is the longest), and `,` returns the length of this substring.
* `n+` stringifies the length and appends a newline to it.

Ps. If the equals signs in the output are optional, the `61` can be omitted (and the `2$` replaced by `1$`), for a total length of **24 bytes**:

```
:s.&{{1$=}s%1,/$-1=,n+}%

```

# Answer
> 6 votes
## CoffeeScript, 109 bytes

I like regex.

```
f=(s)->a={};a[t[0]]=t.length for t in s.match(/((.)\2*)(?!.*\1)/g).reverse();(k+'='+v for k,v of a).join '\n'

```

Here is the compiled JavaScript you can try in your browser's console

```
f = function(s) {
  var a, t, _i, _len, _ref;
  a = {};
  _ref = s.match(/((.)\2*)(?!.*\1)/g).reverse();
  for (_i = 0, _len = _ref.length; _i < _len; _i++) {
    t = _ref[_i];
    a[t[0]] = t.length;
  }
  return a;
};

```

Then you can call

```
f("acbaabbbaaaaacc")

```

to get

```
c=2
a=5
b=3

```

# Answer
> 6 votes
# Python 3, 69 bytes

```
s=input()
for c in set(s):
 i=0
 while-~i*c in s:i+=1
 print(c,'=',i)

```

Try it online!

Even golfed Python can be very readable. I think this code is fully idiomatic except for the `-~i` for `i+1` and the single-letter variables. Thanks to pxeger for saving 1 byte.

Example runs:

```
>>> helloworld
e = 1
d = 1
h = 1
l = 2
o = 1
r = 1
w = 1
>>> acbaabbbaaaaacc
a = 5
c = 2
b = 3

```

# Answer
> 5 votes
# Pyth, 24 25 26 (or 29)

```
=ZwFY{Z=bkW'bZ~bY)p(Yltb

```

Test can be done here: link

Outputs in the format:

```
('a', 5)
('c', 2)
('b', 3)

```

Explanation:

```
=Zw              Store one line of stdin in Z
FY{Z             For Y in set(Z):
=bk              b=''
W'bZ             while b in Z:
~bY              b+=Y
)                end while
p(Yltb           print (Y, len(b)-1)

```

Python:

```
k=""
Z=copy(input())
for Y in set(Z):
 b=copy(k)
 while (b in Z):
  b+=Y
 print(_tuple(Y,len(tail(b))))

```

For proper (a=5) output, use:

```
=ZwFY{Z=bkW'bZ~bY)p++Y"="`ltb

```

29 characters

# Answer
> 5 votes
# C, 126 125 119 bytes

```
l,n,c[256];main(p){while(~(p=getchar()))n*=p==l,c[l=p]=c[p]>++n?c[p]:n;for(l=256;--l;)c[l]&&printf("%c=%d\n",l,c[l]);}

```

Running:

```
$ gcc seq.c 2>& /dev/null
$ echo -n 'acbaabbbaaaaacc' | ./a.out
c=2
b=3
a=5

```

# Answer
> 4 votes
## *Mathematica*, ~~74~~ ~~72~~ 69

```
Print[#[[1,1]],"=",Max[Tr/@(#^0)]]&/@Split@Characters@#~GatherBy~Max&

% @ "acbaabbbaaaaacc"

```

> ```
> a=5
> c=2
> b=3
>
> ```

Not very good but strings are not *Mathematica*'s best area. Getting better though. :-)

# Answer
> 3 votes
# *C#* (LinQPad)

## 146

This is tsavino's answer but shorter. Here, I used `Distinct()` instead of `GroupBy(c=>c)`. Also the curly braces from the `foreach-loop` are left out:

```
void v(string i){foreach(var c in i.Distinct())Console.WriteLine(c+"="+(from Match m in Regex.Matches(i,"["+c+"]+")select m.Value.Length).Max());}

```

---

## 136

I tried using a `lambda expression` instead of the normal query syntax but since I needed a `Cast<Match>` first, the code became 1 character longer... Anyhow, since it can be executed in LinQPad, you can use `Dump()` instead of `Console.WriteLine()`:

```
void v(string i){foreach(var c in i.Distinct())(c+"="+(from Match m in Regex.Matches(i,"["+c+"]+")select m.Value.Length).Max()).Dump();}

```

---

Further study of the code got me thinking about the `Max()`. This function also accepts a `Func`. This way I could skip the `Select` part when using the lambda epxression:

```
void v(string i){foreach(var c in i.Distinct())(c+"="+Regex.Matches(i,"["+c+"]+").Cast<Match>().Max(m=>m.Value.Length)).Dump();}

```

Thus, final result:

# *128*

**Update:**

Thanks to the tip from Dan Puzey, I was able to save another 6 characters:

```
void v(string i){i.Distinct().Select(c=>c+"="+Regex.Matches(i,"["+c+"]+").Cast<Match>().Max(m=>m.Value.Length)).Dump();}

```

Length:

# 122

# Answer
> 2 votes
# Ruby, 58

```
h={}
gets.scan(/(.)\1*/){h[$1]=[h[$1]||0,$&.size].max}
p h

```

Takes input from STDIN, outputs it to STDOUT in the form `{"a"=>5, "c"=>2, "b"=>3}`

# Answer
> 2 votes
# C# in LINQPad - 159 Bytes

Well, at least I beat T-SQL ;P Won't beat anyone else, but I thought I'd share it anyway.

```
void v(string i){foreach(var c in i.GroupBy(c=>c)){Console.WriteLine(c.Key+"="+(from Match m in Regex.Matches(i,"["+c.Key+"]+")select m.Value.Length).Max());}}

```

Usage:

```
v("acbaabbbaaaaacc");

```

Suggestions are always welcome!

# Answer
> 2 votes
# Powershell ~~80~~ ~~77~~ 72

```
$x=$args;[char[]]"$x"|sort -u|%{"$_="+($x-split"[^$_]"|sort)[-1].length}

```

You need to run it on console...

# Answer
> 2 votes
# Perl - 65 71 76 characters

My first code golf!

For each answer, copy to golf.pl and run as:

```
echo acbaabbbaaaaacc | perl golf.pl

```

My shortest solution prints each character as many times as it appears, since that is not prohibited by the rules.

```
$_=$i=<>;for(/./g){$l=length((sort$i=~/$_*/g)[-1]);print"$_=$l
"}

```

My next-shortest solution (85 90 characters) only prints each character once:

```
<>=~s/((.)\2*)(?{$l=length$1;$h{$2}=$l if$l>$h{$2}})//rg;print"$_=$h{$_}
"for keys %h

```

# Answer
> 1 votes
# F# - 106

```
let f s=
 let m=ref(Map.ofList[for c in 'a'..'z'->c,0])
 String.iter(fun c->m:=(!m).Add(c,(!m).[c]+1))s;m

```

In FSI, calling

```
f "acbaabbbaaaaacc"

```

gives

```
val it : Map<char,int> ref =
  {contents =
    map
      [('a', 8); ('b', 4); ('c', 3); ('d', 0); ('e', 0); ('f', 0); ('g', 0);
       ('h', 0); ('i', 0); ...];}

```

However, to print it without the extra information, call it like this:

```
f "acbaabbbaaaaacc" |> (!) |> Map.filter (fun _ n -> n > 0)

```

which gives

```
val it : Map<char,int> = map [('a', 8); ('b', 4); ('c', 3)]

```

# Answer
> 1 votes
## T-SQL (2012) 189 171

Edit: removed `ORDER BY` because rules allow any output order.

Takes input from a CHAR variable, `@a`, and uses a recursive CTE to create a row for each character in the string and figures out sequential occurrences.

After that, it's a simple `SELECT` and `GROUP BY` with consideration for the order of the output.

Try it out on SQL Fiddle.

```
WITH x AS(
    SELECT @a i,''c,''d,0r,1n
    UNION ALL
    SELECT i,SUBSTRING(i,n,1),c,IIF(d=c,r+1,1),n+1
    FROM x
    WHERE n<LEN(i)+2
)
SELECT d+'='+LTRIM(MAX(r))
FROM x
WHERE n>2
GROUP BY d

```

Assigning the variable:

```
DECLARE @a CHAR(99) = 'acbaabbbaaaaacc';

```

Sample output:

```
a=5
c=2
b=3

```

# Answer
> 1 votes
# Haskell - 113 ~~120~~ bytes

```
import Data.List
main=interact$show.map(\s@(c:_)->(c,length s)).sort.nubBy(\(a:_)(b:_)->a==b).reverse.sort.group

```

Tested with

```
$ printf "acbaabbbaaaaacc" | ./sl
[('a',5),('b',3),('c',2)]

```

# Answer
> 1 votes
# Javascript, 116 bytes

```
y=x=prompt();while(y)r=RegExp(y[0]+'+','g'),alert(y[0]+'='+x.match(r).sort().reverse()[0].length),y=y.replace(r,'')

```

Sample output:

```
lollolllollollllollolllooollo
l=4
o=3

acbaabbbaaaaacc
a=5
c=2
b=3

helloworld
h=1
e=1
l=2
o=1
w=1
r=1
d=1

```

# Answer
> 1 votes
# JavaScript - 91

```
for(i=0,s=(t=prompt()).match(/(.)\1*/g);c=s[i++];)t.match(c+c[0])||alert(c[0]+'='+c.length)

```

**EDIT:** My first solution obeys the rules, but it prints several times single char occurrences like `abab` =\> `a=1,b=1,a=1,b=1` so I came out with this (**101** chars), for those not satisfied with my first one:

```
for(i=0,s=(t=prompt()).match(/((.)\2*)(?!.*\1)/g);c=s[i++];)t.match(c+c[0])||alert(c[0]+'='+c.length)

```

# Answer
> 1 votes
# JavaScript \[83 bytes\]

```
prompt().match(/(.)\1*/g).sort().reduce(function(a,b){return a[b[0]]=b.length,a},{})

```

Run this code in the browser console.

For input "`acbaabbbaaaaacc`" the console should output "`Object {a: 5, b: 3, c: 2}`".

# Answer
> 1 votes
# Jelly, 12 bytes

```
ŒriƇṀj”=ʋⱮQY

```

Try it online!

-2 bytes thanks to Unrelated String!

8 bytes to output as a list of pairs

## How it works

```
ŒriƇṀj”=ʋⱮQY - Main link. Takes a string S on the left
        ʋ    - Group the previous 4 links into a dyad f(S, C):
Œr           -   Run-length encode S
   Ƈ         -   For each sublist in rle(S), keep it if:
  i          -     It contains C
    Ṁ        -   Maximum
                 As all elements are in the form [C, n] for integers n,
                 Python considers the maximum as the greatest n
     j”=     -   Join with "="; Yields [C, "=", n]
          Q  - Get the unique characters of S
         Ɱ   - For each unique character C in S, yield f(C, S)
           Y - Join by newlines and output

```

# Answer
> 1 votes
# Husk, 18 bytes

```
mȯJ'=§eo;←osL►Lk←g

```

Try it online!

11 bytes if we ignore the exact input format and display as a list of pairs instead.

# Answer
> 1 votes
# Husk, 16 bytes

```
mS:(:'=s▲`mg¹#)U

```

Try it online!

**Explanation:**

```
m              U    # for each of the unique elements of the input
 S:                 # prepend the element to
   (:'=       )     # '=' prepended to
        ▲           # the maximum of
             #      # the number of times it occurs in
         `mg¹       # each group of identical items in the input,
       s            # converted into a string

```

I saw that Razetime had answered this in Husk, so I had to have a go too...

# Answer
> 1 votes
## Bash / GNU core utils (40)

```
fold -1|uniq -c|sort -k2 -k1r|uniq -f1

```

Try it online!

Output when input is "acbaabbbaaaaacc":

```
      5 a
      3 b
      2 c

```

Explanation:

* `fold -1` adds a newline after each character
* `uniq -c` counts the number of consecutive identical lines
* `sort -k2 -k1r` sorts the result so as the maximum count for each character comes first
* `uniq -f1` keeps only the first line for each character

# Answer
> 0 votes
## Python 3, 88 bytes

```
from re import*;a=input();[(i[0],len(max(i))) for i in(findall(l+"+",a)for l in set(a))]

```

Outputs in a format of:

```
[('b', 3), ('c', 2), ('a', 5)]

```

# Answer
> 0 votes
# Python3 - ~~111~~, ~~126~~, ~~115~~ ~~114~~ 111 bytes

Executable code that will read 1 line (only use lowercase letters a-z)

```
d={}.fromkeys(map(chr,range(97,123)),0)
for c in input():d[c]+=1
[print("%s=%d"%(p,d[p]))for p in d if d[p]>0]

```

Edit: Excluded unnecessary output on request from @Therare

The output looks nice

```
~/codegolf $ python3 maxseq.py
helloworld
l=3
o=2
h=1
e=1
d=1
w=1
r=1

```

# Answer
> 0 votes
# Julia, 85

```
f(s)=(l=0;n=1;a=Dict();[c==l?n+=1:(n>get(a,l,1)&&(a[l]=n);n=1;l=c) for c in s*" "];a)
julia> f("acbaabbbaaaaacc")
{'a'=>5,'c'=>2,'b'=>3}

```

# Answer
> 0 votes
# JavaScript - 141 137 125

I don't like regex :)

```
function g(a){i=o=[],a=a.split('');for(s=1;i<a.length;){l=a[i++];if(b=l==a[i])s++;if(!b|!i){o[l]=o[l]>s?o[l]:s;s=1}}return o}

```

Run

```
console.log(g("acbaabbbaaaaacc"));

```

outputs

```
[ c: 2, a: 5, b: 3 ]

```

# Answer
> 0 votes
# Javascript, 109 104 100 98 bytes

```
function c(s){q=l={};s.split('').map(function(k){q[k]=Math.max(n=k==l?n+1:1,q[l=k]|0)});return q}

```

Example usage:

```
console.log(c("aaaaaddfffabbbbdb"))

```

outputs:

```
{ a: 5, d: 2, f: 3, b: 4 }

```

# Answer
> 0 votes
# PHP, 104 102 96

```
<?php function _($s){while($n=$s[$i++]){$a[$n]=max($a[$n],$n!=$s[$i-2]?$v=1:++$v);}print_r($a);}

```

usage

```
_('asdaaaadddscc');

```

printed

```
Array ( [a] => 4 [s] => 1 [d] => 3 [c] => 2 )

```

# Answer
> 0 votes
**Java 247**

```
import java.util.*;public class a{public static void main(String[]a){Map<Character, Integer> m = new HashMap<>();for(char c:a[0].toCharArray()){Integer v=m.get(c);m.put(c,v==null?1:v+1);}for(char c:m.keySet())System.out.println(c+"="+m.get(c));}}

```

# Answer
> 0 votes
## R (219, 213, 197, 196, 191, 165, 169, 157, 163 characters)

The `data.table` version added. There was an error in the previous `data.table` version.

**Golfed `data.table` version (163)**

```
require(data.table);f=function(x){x=strsplit(x,"")[[1]];data.table(x=x,y=cumsum(c(1,x[-1]!=head(x,-1))))[,.N,list(x,y)][order(-N)][!duplicated(x),paste0(x,"=",N)]}

```

**Ungolfed `data.table` version**

```
require(data.table)
f <- function(x) {
  x <- strsplit(x, "")[[1]]
  data.table(a=x, y=cumsum(c(1, x[-1] != head(x, -1))))[
  , .N, list(a, y)][order(-N)][!duplicated(a), paste0(a, "=", N)]
}

```

---

**Golfed `data.frame` version (174)**

```
f=function(x){x=strsplit(x,"")[[1]];d=data.frame(a=x,y=cumsum(c(1,x[-1]!=head(x,-1))));d=aggregate(d$y,d,length);d=d[order(-d$x),];d=d[!duplicated(d$a),];paste0(d$a,"=",d$x)}

```

**Ungolfed `data.frame` version**

```
f <- function(x) {
  x <- strsplit(x, "")[[1]]
  d <- data.frame(a = x, y = cumsum(c(1, x[-1] != head(x, -1))))
  d <- aggregate(d$y, d, length)
  d <- d[order(-d$x), ]
  d <- d[!duplicated(d$a), ]
  paste0(d$a, "=", d$x)
}

f("acbaabbbaaaaacc")
f("acbaabbbaaaaaccdee")

```

# Answer
> 0 votes
## C 169

Iterates each printable character in ASCII table and counts max from input string.

```
#define N 128
int c,i,n;
char Y[N],*p;
int main(){gets(Y);
for(c=33;c<127;c++){p=Y;n=0,i=0;while(*p){if(*p==c){i++;}else{n=(i>n)?i:n;i=0;}p++;}
if(n>0) printf("%c=%d\n",c,n);}
}

```

# Answer
> 0 votes
# JavaScript 116

```
prompt(x={}).replace(/(.)\1*/g,function(m,l){n=m.length
if(!x[l]||x[l]<n)x[l]=n})
for(k in x)console.log(k+'='+x[k])

```

# Answer
> 0 votes
## Groovy - 80 chars

Based on this clever answer by xnor :

```
t=args[0];t.toSet().each{i=0;
while(t.contains(it*++i));
println "${it}=${i-1}"}

```

Output:

```
$ groovy Golf.groovy abbcccdddd
d=4
b=2
c=3
a=1

```

Ungolfed:

```
t=args[0]

t.toSet().each { c ->
    i=0
    s=c

    // repeat the char c with length i
    // e.g. "b", "bb", "bbb", etc
    // stop when we find a length that is not in t:
    // this is the max + 1
    while (t.contains(s)) {
        i++
        s=c*i
    }
    println "${c}=${i-1}"
}

```

# Answer
> 0 votes
# Javascript (E6) 103

A javascript solution that cares about the requested output format.

```
F=a=>(p=q={},m={},[...a].map(x=>(x!=p&&(q[p=x]=0),m[x]>++q[x]?0:m[x]=q[x])),''+[i+'='+m[i]for(i in m)])

```

**Ungolfed**

```
F=a=>(
  p=q={}, m={},
  [...a].map(
    x=>(
      x!=p && (q[p=x]=0),
      m[x] > ++q[x] ? 0 : m[x] = q[x]
    )
  ),
  '' + [i+'='+m[i] for(i in m)]
)

```

**Test**

In Firefox console

```
console.log(F("aaaaaddfffabbbbdb"))

```

> a=5,d=2,f=3,b=4

# Answer
> 0 votes
It's written in Python, in order to run the code, just call thefunction maxsequence(str). For instance, `maxsequence('aaaaaannndmdejlsfnsfsssssnnnnnxxx')` or `maxsequence("kdkdkdkdjeeeiwwwnnnmdnnsbjdiiiiiiiiiidndbbcbbccbcvcvdddcjdjdjwwwwwwkkkkxlxllllllll")`

```
def maxsequence(str):

    count = 1 # count if the letters are repeat
    step = 0 # once the next letter changed, step = count.
    countArray = [] # put all the sequence numbers in an array
    lettersArray = [] # put all the repeat letters in an array
    max = 0
    # for calculating the max of the array, it needs two indexes to do that
    indexFirst = 0
    indexNext = 1
    i = 0
    while(i<len(str) and i<=(len(str)-2)):
        if(str[i]==str[i+1]):
            count += 1
            step = count
        else:
            lettersArray.append(str[i])
            step = count
            countArray.append(step)
            count = 1
        i += 1
    countArray.append(step)
    lettersArray.append(str[i])

    while(countArray[indexFirst]>=countArray[indexNext] and indexNext<(len(countArray)-1)):
        indexNext += 1
        if(countArray[indexFirst]<=countArray[indexNext]):
            indexFirst = indexNext
    max = countArray[indexFirst]

    for i in range(len(lettersArray)):
        print lettersArray[i],"=",countArray[i]

    print "The max sequence is:", max
    return max

```

# Answer
> 0 votes
# Scala – 99 as program, 97 as function

Program (reads one line from stdin)

```
for((k,v)<-"(.)\\1*".r.findAllIn(Console.in.readLine).toSeq.groupBy(_(0)))println(k+"="+v.max.size)

```

Function:

```
def f(s:String)=for((k,v)<-"(.)\\1*".r.findAllIn(s).toSeq.groupBy(_(0)))println(k+"="+v.max.size)

```

# Answer
> 0 votes
## Clojure - 105 bytes

I'm learning Clojure at the moment and what would be a better way to do it than golfing? So, here's my second entry to this challenge.

```
(def f #(apply str(for[c(distinct %)](str c\=(apply max(map count(re-seq(re-pattern(str c\+))%)))"\n"))))

```

Examples:

```
=> (f "acbaabbbaaaaacc")
"a=5\nc=2\nb=3\n"
=> (f "aaaabaa")
"a=4\nb=1\n"
=> (println (f "acbaabbbaaaaacc"))
a=5
c=2
b=3

```

# Answer
> 0 votes
## J 45

```
~.,.'=',.":@({.@>>.//.$&>)@(<;.2~2&(~:/\),1:)

```

As a verb. Though for using it , you'd need to assign it to a name, eg:

```
f=:~.,.'=',.":@({.@>>.//.$&>)@(<;.2~2&(~:/\),1:)
f 'acbaabbbaaaaacc'
a=5
c=2
b=3

```

Short explanation:

```
                                @(        2&(~:/\),1:): find where neighbors are different
                                   <;.2~              : cut in these places
            (              $&> )                      : get the length of the string in the box
             ({.@>)                                   : get the first letter from the box
                   (>./)/.                            : get the maximum for each unique char
~.,.'=',.":@(                  )                      : Output: letter = stringified value

```

# Answer
> 0 votes
## BACCHUS, 41

```
'acbaabbbaaaaacc'j:A=·z#:B=($A,$0h:a(·>0.$0,'=',·+)?),$B¨n

```

I have discounted the actual parameter String.

Explanation

`j:A=` Transform the String in a block (some sort of array) and stores it in `A` variable.

`·z#:B=` Read last value on the stack (the block) and removes al duplicates, storing it in `B`.

`(` Open for each

`$A,$0h:a` counts how many times the current element of the for each is present in A (read as a String) and pushes this value to Stack (this avoid inmediate printing of the value).

`(` Open if

`·>0.` is last value is \> 0 then

`$0,'=',·+` Concatenates current for each element, '=' and last value in stack (that will be printed out)

`)?` Close if

`,$B¨` Close for each indicating the block to loop over (`B`).

`n` Indicates that the output must be space separated

# Answer
> 0 votes
## Clojure, 107 bytes

```
#(apply str(for[p(vals(group-by last(partition-by(fn[i]i)%)))](str(ffirst p)\=(apply max(map count p))\,)))

```

Returns `"a=5,c=2,b=3,"` for the example input. This would have been 89 bytes, returning `([\a 5] [\c 2] [\b 3])`:

```
#(for[p(vals(group-by last(partition-by(fn[i]i)%)))][(ffirst p)(apply max(map count p))])

```

# Answer
> 0 votes
# APL (Dyalog), 41 bytes

```
{(⊃,'=',⍕∘≢)¨l[∪⍳⍨⊃¨l←n[⍒≢¨n←⍵⊂⍨1,2≠/⍵]]}

```

Try it online!

Ungolfed:

```
{
  n←⍵⊂⍨1,2≠/⍵
  l←n[⍒≢¨n]
  (⊃,'=',⍕∘≢)¨l[∪⍳⍨⊃¨l]
}

```

`{` anonymous function

`2≠/⍵` pair-wise sliding window inequality of the argument
`1,` prepend a one
`⍵⊂⍨` use that to partition the argument
`n←` store in *n*

`n[``]` index *n* with:
the descending order of
`≢¨` the length of each element in
argument
`l←` store in *l*

`l[``]` index *l* with:
the unique of
`⍳⍨` the first occurrence of each element of
`⊃¨l` the first element of each of *l*
`(` apply the following tacit function on each element
the first element
`,` concatenated to
`'='` an equal sign
`,` concatenated to
`⍕∘≢` the formatted length

`}`

# Answer
> 0 votes
# 05AB1E, 17 bytes

```
ÙvIγʒyå}€gZy…ÿ=ÿ,

```

Try it online!

```
ÙvIγʒyå}€gZy…ÿ=ÿ,   Argument s
Ùv                  For each c in s uniquified
  Iγ                Split s into chunks of consecutive equal elements
    ʒyå}            Filter: Keep elements that contain c
        €g          Map to element length
          Z         Get max
           y…ÿ=ÿ,   Print "c=max"

```

# Answer
> 0 votes
# Java, 192 bytes

```
import java.util.*;s->{int p=0,c=0;Map<Character,Integer>m=new HashMap();for(byte b:s.getBytes()){c=p==b?c+1:1;m.merge((char)(p=b),c,Math::max);}m.forEach((k,v)->System.out.println(k+"="+v));}

```

Try it online!

## Java, 251 bytes (with regular expressions)

```
import java.util.regex.*;import java.util.function.*;s->{Matcher m=Pattern.compile("(.)\\1*").matcher(s);Map<String,Integer>a=new HashMap();while(m.find())a.merge(m.group(1),m.group().length(),Math::max);a.forEach((k,v)->System.out.println(k+'='+v));}

```

Try it online!

# Answer
> -1 votes
Java Code: Out of interest I just found a solution will further enhance soon.

```
import java.util.HashMap;

```

import java.util.Map.Entry; import java.util.Scanner;

public class MaxSequenceLength { private HashMap characterCount = new HashMap\<\>();

```
public static void main(String[] args) {
    Scanner inputScanner = new Scanner(System.in);
    new MaxSequenceLength().validateInput(inputScanner.nextLine());
    inputScanner.close();
}

private void validateInput(String inputString) {
    if (inputString.length() <= 1024) {
        scanInput(inputString.toCharArray());
    }
}

private void scanInput(char[] characterArrayInput) {
    for (char tempCharacter : characterArrayInput) {
        if ((int) tempCharacter < 65
                || ((int) tempCharacter > 90 && (int) tempCharacter < 97)
                || (int) tempCharacter > 122) {
            continue;
        } else if (characterCount.containsKey(tempCharacter)) {
            characterCount.put(tempCharacter,
                    characterCount.get(tempCharacter) + 1);
        } else {
            characterCount.put(tempCharacter, 1);
        }
    }
    for (Entry<Character, Integer> tempEntry : characterCount.entrySet()) {
        System.out.println(tempEntry.getKey() + " = "
                + tempEntry.getValue());
    }
}

```

}

The code would ignore all the other symbols and give only case sensitive character output.

# Answer
> -2 votes
## Python (~~62~~ 55)

```
n=raw_input()
print map(lambda x:[x,n.count(x)],set(n))

```

Old answer:

```
n=raw_input()
s=set(n)
print zip(s,map(lambda x:[x,n.count(x)],s))

```

---
Tags: code-golf, string
---


title: What's next, Achilles?

text:
# Question
Title: What's next, Achilles?
Powerful numbers are positive integers such that, when expressed as a prime factorisation:

$$a = p\_1^{e\_1} \times p\_2^{e\_2} \times p\_3^{e\_3} \cdots \times p\_k^{e\_k}$$

all exponents \\$e\_1, e\_2, ...\\$ are greater than or equal to \\$2\\$. Note that the exponents do not include zero exponents, as exampled by \\$200 = 2^3 \times 3^0\times 5^2 = 2^3 \times 5^2\\$ being a powerful number. This includes all perfect powers, and a few "extra" numbers that are not perfect powers.

Achilles numbers are powerful numbers that are not perfect powers. The smallest Achilles number is \\$72 = 2^3 \times 3^2\\$. The Achilles numbers less than or equal to \\$500\\$ are \\$72, 108, 200, 288, 392, 432\\$ and \\$500\\$.

You are to take an Achilles number as input and output the smallest Achilles number greater than the input.

You may input and output in any convenient method. This is so the shortest code in bytes wins

## Test Cases

```
input output
   72    108
  108    200
  200    288
  800    864
 1152   1323
 4500   4563
 3456   3528
 4563   4608
43808  43904
90828  91592
28800  29403
64800  64827
29768  30375

```

The program I used to generate these test cases. Contains spoilers for anyone who can understand Jelly.

# Answer
# Jelly, 12 bytes

```
‘ÆEg/ḟ$f1Ʋ1#

```

A full program which prints the next Achilles number.

**Try it online!** Or see the test-suite.

### How?

```
‘ÆEg/ḟ$f1Ʋ1# - Main Link: Archiles number (or any integer), n
‘            - increment (n)
          1# - find the first k (starting at k=n+1) for which:
         Ʋ   -   last four links as a monad - i.e. f(k):
 ÆE          -     prime exponent vactor (e.g k=400 -> [3,0,2] since 2^3+3^0+5^2)
      $      -     last two links as a monad:
    /        -       reduce by:
   g         -         Greatest Common Divisor -> x
     ḟ       -      filter discard (from [x] if in ÆE result)
        1    -     one
       f     -     filter keep (i.e. [1] if g/ was 1 and 1 not in ÆE result)
                   (empty list is falsey, so we keep incrementing k until we get [1])

```
> 7 votes

# Answer
# , 26 bytes

```
_(]+1-1</@(=],+./)q:)^:_>:

```

Try it online!

I started with the "do-until" idiom `f^:g^:_` with `g` boolean (apply `f` while `g` is true), but soon realized that the "find next integer" can be written in a single fixpoint `(]+1-g)^:_`. The only problem is that we don't have a straightforward/more golfy way to express the boolean negation of `g` other than `1-g`.

### How it works

```
_(]+1-1</@(=],+./)q:)^:_>:  NB. Input: n
                        >:  NB. n+1
_(                  )^:_    NB. Fixpoint with left arg of _ (infinity)...
                  q:    NB. (_ q: n) gives prime exponents including zeros
                        NB. _ q: 700 -> 2 0 2 1 (2^2 * 5^2 * 7^1)
          ( ],+./)      NB. Append GCD of ^ to itself
      1    =            NB. Test if each number equals 1 (gives boolean vector)
       </@   NB. Test if the only 1 is the last item
  ]+1-       NB. Negate the condition and add to the input number

```
> 7 votes

# Answer
# JavaScript (ES6),  ~~117 ... 99~~  98 bytes

```
f=n=>(d=1,h=(n,x)=>++d>n?~x:1/(g=_=>q=n%d?0:g(n/=d)-1)(G=x=>q?G(q,q=x%q):x)|h(n,G(x)))(++n)?f(n):n

```

Try it online!

### Commented

```
f = n => (              // f is a recursive function taking n
  G = x =>              // G is a helper function computing GCD(x, q)
    q ? G(q, q = x % q) // (NB: actually defined in a dummy argument
      : x,              // passed to g in the last golfed version)
  d = 1,                // initialize the divisor d
  h = (                 // h is a recursive function taking:
    n,                  //   n = updated value
    x                   //   x = GCD of the exponents (but negative)
  ) =>                  //
    ++d > n ?           // increment d; if it's greater than n:
      ~x                //   stop and yield -x - 1
    :                   // else:
      1 / (g = _ =>     //   g is yet another recursive function
        q =             //   which computes q:
          n % d ?       //   the opposite of the number of times n can be
            0           //   divided by d
          :             //
            g(n /= d)   //   we compute 1 / g() followed by a bitwise OR
            - 1         //   to make sure that q is not equal to -1
      )() |             //
      h(                //   recursive call to h:
        n,              //     updated value of n
        G(x)            //     x = GCD(x, q)
      )                 //   end of recursive call
)(++n) ? f(n)           // if the result of h is truthy, try again
       : n              // otherwise, return n

```
> 6 votes

# Answer
# Jelly, ~~14~~ 13 bytes

```
‘‘ÆE’Pȧg/Ʋ’Ɗ¿

```

Try it online!

Did not look at the linked Jelly answer, but that byte count does look familiar... until I remembered how I was originally checking the GCD anyhow

edit: they're not even remotely alike what the hell

```
‘                Starting at 1 more than the input,
 ‘         Ɗ¿    increment while:
  ÆE     Ʋ       for the exponents of the prime factorization,
     P           the product of
    ’            each minus 1
      ȧ          logical-AND
       g/        their greatest common denominator
          ’      is not equal to 1.

```
> 5 votes

# Answer
# Pyth, ~~20~~ 18 bytes

```
f&!}1J/LPTPTqiFJ1h

```

Try it online!

*-2 bytes thanks to FryAmTheEggman!*

---

Explanation:

```
f                hQ | first integer T starting at input + 1 such that
      /LPTPT        | each prime factor's count in the prime factor list of T
     J              | (this list will be called J)
  !}1               | does not contain 1
 &                  | AND
             iFJ    | the GCD of all of the elements of J
            q   1   | equals 1

```
> 5 votes

# Answer
# Husk, ~~17~~ ~~19~~ ~~18~~ 14 bytes

~~Fixed thanks to Giuseppe but had to add 2 bytes~~. As Neil and caird coinheringaahing pointed out, not only was my second condition unnecessary, my third condition was just plain wrong. Hopefully it's fixed now.

```
ḟö§¤>ε▼F⌋mLgp→

```

Try it online!

```
ḟö§¤>ε▼F⌋mLgp→
             → Increment input
ḟ              Find the smallest number greater than or equal to n+1 matching this condition:
            p    Prime factorization
           g     Group equal adjacent elements
         m       Map each to
          L       its length (the powers)
  §             Fork (apply two functions to the powers and then combine the results)
      ▼          First function: Minimum power
       F         Second function: Reduce with
        ⌋         gcd
   ¤>ε           Function to combine with:
   ¤              Apply one function to both arguments, then combine with another function
     ε             Check if equal to 1 (1 if 1, 0 otherwise)
    >              Ensure the minimum is not 1, but the gcd is.

```
> 5 votes

# Answer
# 05AB1E, 12 bytes

A port of Bubbler's J answer.

```
∞+.ΔÓD¿ªΘ.«‹

```

Try it online!

```
∞            # push an infinite list of numbers [1,2,3,...]
 +           # add the input to each number
  .Δ         # find the first integer in this list that satisfies:
    Ó        # the exponents of the prime factorization (including 0's)
     D       # duplicate this list
      ¿      # take the gcd
       ª     # and append it to the exponents
        Θ    # for each value: is it equal to 1?
         .«  # right reduce this list of 0's and 1's
           ‹ # with a < b, this is only 1 if the list had a single 1 at the end

```

The same length without the  builtin:

```
[>DÓD¿ªΘ.«‹#

```

Try it online!
> 5 votes

# Answer
# Retina 0.8.2, ~~157~~ 115 bytes

```
.+
$*11
+`^(1+)((\1(1+))(?=(\3*)\1*$)\3*(?=\4$\5))+1$|^(?!((?=(11+?)\7*$)((?=\7+$)(?=(1+)(\9+)$)\10){2,})+1$)
1$&
1

```

Try it online! No test suite because it would be too slow. Explanation:

```
.+
$*11

```

Convert to unary and add 1.

```
+`

```

Repeat while...

```
^(1+)((\1(1+))(?=(\3*)\1*$)\3*(?=\4$\5))+1$|

```

... the current value is a perfect power, or...

```
^(?!((?=(11+?)\7*$)((?=\7+$)(?=(1+)(\9+)$)\10){2,})+1$)

```

... the current value is not powerful...

```
1$&

```

... increment the value.

```
1

```

Convert to decimal.

I'm currently testing whether a number is powerful based on taken from my answer to Is it almost-prime? except here I divide at least twice by each (prime) factor and then repeat until all factors have been consumed. In theory it should be possible to take any factors and divide at least twice by each, but for some reason I don't seem to be able to adapt the expression for perfect powers to match a product of perfect powers.
> 4 votes

# Answer
# Java, ~~194~~ ~~167~~ ~~160~~ 152 bytes

*Saved 7 bytes thanks to ceilingcat*

*Saved 8 bytes thanks to user*

```
int a(int n){return p(++n)!=1?a(n):n;}int p(int n){for(int i=1,o=n,c,z;++i<o;){for(c=z=1;n%i<1;c++)n/=i;while(z<o)z*=i;if(c==2|z==o)return 0;}return n;}

```

Try it online!
> 4 votes

# Answer
# Brachylog, ~~17~~ 16 bytes

```
<.ḋḅ{{Ṁlf⊇}ᵛ!}Ȯ∧

```

Try it online!

Looked like it might compete with Jelly until I realized where I'd have to put that cut! Trying to see if maybe I could do not-a-perfect-power checking without going through the factors of the prime exponents.

```
 .                  The output
<                   is a number strictly greater than the input
   ḅ                of which the runs of
  ḋ                 the prime factors
     {    }ᵛ        each
      Ṁ             contain at least two elements,
        f           and the factors of
       l            the lengths of which
    {    ⊇ ᵛ!}      have a largest common subset
               ∧    (not necessarily equal to the output)
              Ȯ     which contains only one element.

```
> 3 votes

# Answer
# Japt, 24 bytes

Definitely struggled to cut this short since some of the operations are bulky by themselves, for example getting the exponents.

```
_=k ü mÊ;Zry ¶1©Ze¨2}aUÄ
                      UÄ // Starting at input plus one,
                     a   // find the next integer that returns true when
_                   }    // run through the function:
 =                       // Z =
  k                      // prime factors
    ü                    // grouped by value
      mÊ                 // and mapped to length, e.g. the exponents of prime factors.
        ;                // Return whether
         Zry ¶1          // GCD of Z equals 1
               ©         // and
                Ze¨2     // every member of Z is geq 2.

```

Try it out here.
> 2 votes

---
Tags: code-golf, math, number-theory
---


title: Python Prime Problem

text:
# Question
Title: Python Prime Problem
Your challenge is to write a Python program to print all the primes (separated by whitespace) less than a given integer `N` with an asterisk (`*`) next to each twin prime in **ONE statement**. A twin prime is a prime number that is either two more or two less than another prime.

All output should be to stdout and input should be read from stdin. (Hardcoding outputs is allowed, but it is not likely to result in very short code.)

Shortest code wins!

For the less restricted version of the challenge for all languages, click here.

## Input

* `N` is always one of 50, 100, 1000, 1000000, or 10000000

## Output

* Possible output for input `12` could be
```
2 3* 5* 7* 11*
```
(However, the input will never be 12, as specified above. Your program need not work for this input.)

## Restrictions

* No new lines or semicolons
* Do not use eval or exec

# Answer
> 5 votes
# Python 3.8 (pre-release), 119 bytes

```
print(*[str(i)+'*'*(p(i-2)|p(i+2))for i in range(2,int(input()))if(p:=lambda x:all(x%i for i in range(2,x))*(x>1))(i)])

```

Reads from stdin.

Try it online!

---
Tags: code-golf, restricted-source, primes, python
---


title: Avoiding Rivers

text:
# Question
Title: Avoiding Rivers
## Background

In typography, *rivers* are visual gaps in a block of text, which occur due to coincidental alignment of spaces. These are particularly annoying since your brain seems to pick them up more easily in peripheral vision, which constantly distracts your eyes.

As an example, take the following block of text, lines broken such that the line width does not exceed **82 characters**:

```
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui
officia deserunt mollit anim id est laborum. Lorem ipsum dolor sit amet,
consectetur adipisicing elit, sed do eismod tempor incididunt ut labore et dolore
maga aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris
nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in
voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint
occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id
est laborum.

```

There is a river spanning six lines in the bottom right part, which I've highlighted in the following block:

```
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui
officia deserunt mollit anim id est laborum. Lorem█ipsum dolor sit amet,
consectetur adipisicing elit, sed do eismod tempor█incididunt ut labore et dolore
maga aliqua. Ut enim ad minim veniam, quis nostrud█exercitation ullamco laboris
nisi ut aliquip ex ea commodo consequat. Duis aute█irure dolor in reprehenderit in
voluptate velit esse cillum dolore eu fugiat nulla█pariatur. Excepteur sint
occaecat cupidatat non proident, sunt in culpa qui█officia deserunt mollit anim id
est laborum.

```

We can mitigate this by choosing a slightly different column width. E.g. if we layout the same text using lines no longer than **78 characters**, there is no river longer than two lines:

```
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis
nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore
eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt
in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor
sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut
labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis
aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in
culpa qui officia deserunt mollit anim id est laborum.

```

Note that for the purpose of this question we're only considering monospaced fonts, such that rivers are simply vertical columns of spaces. The length of a river is the number of lines it spans.

Aside: If you're interesting in river detection in proportional fonts, there are some interesting posts around the network.

## The Challenge

You're given a string of printable ASCII characters (code point 0x20 to 0x7E) - i.e. a single line. Print this text, with a line width between 70 and 90 characters (inclusive), such that the *maximum* length of any river in the text is minimised. If there are multiple text widths with the same (minimal) maximum river length, choose the narrower width. The above example with 78 characters is the correct output for that text.

To break lines, you should replace space characters (0x20) with line breaks, such that the resulting lines have as many characters as possible, but not more than the chosen text width. Note that the resulting line break itself is not part of that count. As an example, in the last block above, `Lorem[...]tempor` contains 78 characters, which is also the text's width.

You may assume that the input will not contain consecutive spaces, and won't have leading or trailing spaces. You may also assume that no word (consecutive substring of non-spaces) will contain more than 70 characters.

You may write a program or function, taking input via STDIN, command-line argument or function argument and printing the result to STDOUT.

This is code golf, so the shortest answer (in bytes) wins.

# Answer
# CJam, ~~116 106 99 84 77~~ 72 bytes

```
l:X;93,72>{:D;OOXS/{S+_2$+,D<{+}{@@);a+\}?}/a+}%{z'K*S/:!0a/1fb$W=}$0=N*

```

Takes the single line input and prints the correct output to STDOUT.

*UPDATE* : Improved a lot and removed redundant loops by doing all calculations in the sorting loop itself. Also fixed a bug in river length calculation.

Explanation soon (after I golf it even further)

Try it here
> 7 votes

# Answer
## Ruby ~~162 160 158 152 160~~ 157 (demo)

```
i=gets+' '
(69..s=r=89).map{|c|w=i.scan(/(.{1,#{c}}\S) /).flatten
m=(0..c).map{|i|w.map{|l|l[i]}+[?x]}.join.scan(/ +/).map(&:size).max
m<s&&(s=m;r=w)}
puts r

```

The un-golfed version:

```
input = gets+' '

result = ''

(69..smallest_max=89).each{|w|
  #split text into words of at most w characters
  wrap = (input+' ').scan(/(.{1,#{w}}\S) /).flatten

  #transpose lines and find biggest "river"
  max_crt_river = (0..99).map{|i| wrap.map{|l|l[i]} }.flatten.join.scan(/ +/).max_by(&:size).size

  if max_crt_river < smallest_max
    smallest_max = max_crt_river
    result = wrap.join ?\n
  end
}
puts result

```
> 13 votes

# Answer
# Bash+coreutils, 236 157 bytes

Edited with a different approach - quite a bit shorter than before:

```
a=(`for i in {71..91};{
for((b=1;b++<i;));{
fold -s$i<<<$@|cut -b$b|uniq -c|sort -nr|grep -m1 "[0-9]  "
}|sort -nr|sed q
}|nl -v71|sort -nk2`)
fold -s$a<<<$@

```

Reads the input string from the command line.

With 3 nested sorts, I shudder to think what the big-O time complexity is for this, but it does complete the example in under 10 seconds on my machine.
> 8 votes

# Answer
## APL (105)

```
{∊{1↓∊⍵,3⊃⎕TC}¨⊃G/⍨V=⌊/V←{⌈/≢¨⊂⍨¨↓⍉2≠⌿+\↑≢¨¨⍵}¨G←(K⊂⍨' '=K←' ',⍵)∘{×⍴⍺:(⊂z/⍺),⍵∇⍨⍺/⍨~z←⍵>+\≢¨⍺⋄⍺}¨70+⍳21}

```

Explanation:

* `(K⊂⍨' '=K←' ',⍵)`: Add a space in front of , then split  on the spaces. Each word retains the space it begins with.
* `∘{`...`}¨70+⍳21`: with that value, for each number in the range `[71, 91]`: (Because of the way the words are split, each 'line' ends up with an extra space on the beginning, which will be removed later. The range is shifted by one to compensate for the extra space.)
    + `×⍴⍺:`: if there are still words left,
        - `z←⍵>+\≢¨⍺`: get the length for each word, and calculate a running total of the length, per word. Mark with a `1` all the words that can be taken to fill up the next line, and store this in `z`.
        - `(⊂z/⍺),⍵∇⍨⍺⍨~z`: take those words, and then process what's left of the list.
    + `⋄⍺`: if not, return  (which is now empty).
* `G←`: store the list of lists of lines in `G` (one for each possible line length).
* `V←{`...`}¨G`: for each possibility, calculate the length of the longest river and store it in `V`:
    + `+\↑≢¨¨⍵`: get the length of each word (again), and make a matrix out of the lengths. Calculate the running total for each line on the rows of the matrix. (Thus, the extra space at the beginning of each line is ignored.)
    + `2≠⌿`: for each *column* of the matrix, see if the current length of the line at that point does not match the line after it. If so, there is *not* a river there.
    + `⊂⍨¨↓⍉`: split each column of the matrix by itself (on the `1`s). This gives a list of lists, where for each river there will be a list `[1, 0, 0, ...]`, depending on the length of the river. If there is no river, the list will be `[1]`.
    + `⌈/≢¨`: get the length of each river, and get the maximum value of that.
* `⊃G/⍨V=⌊/V`: from `G`, select the first item for which the length of the longest river is equal to the minimum for all items.
* `{1↓∊⍵,3⊃⎕TC}¨`: for each line, join all of the words together, remove the fist item (the extra space from the beginning), and add a newline to the end.
* : join all the lines together.
> 8 votes

# Answer
# Python 3, 329 bytes

```
import re,itertools as s
def b(t,n):
 l=0;o=""
 for i in t.split():
  if l+len(i)>n:o=o[:-1]+'\n';l=0
  l+=len(i)+1;o+=i+' '
 return o
t=input();o={}
for n in range(90,69,-1):o[max([len(max(re.findall('\s+',x),default='')) for x in ["".join(i) for i in s.zip_longest(*b(t,n).split('\n'),fillvalue='')]])]=n
print(b(t,o[min(o)]))

```

Ungolfed version:

```
# Iterates over words until length > n, then replaces ' ' with '\n'
def b(t,n):
    l = 0
    o = ""
    for i in t.split():
        if l + len(i) > n:
            o = o[:-1] + '\n'
            l = 0
        l += len(i) + 1
        o += i + ' '
    return o

t = input()
o = {}
# range from 90 to 70, to add to dict in right order
for n in range(90,69,-1):
    # break text at length n and split text into lines
    temp = b(t,n).split('\n')
    # convert columns into rows
    temp = itertools.zip_longest(*temp, fillvalue='')
    # convert the char tuples to strings
    temp = ["".join(i) for i in temp]
    # findall runs of spaces, get longest run and get length
    temp = [len(max(re.findall('\s+',x),default='')) for x in temp]
    # add max river length as dict key, with line length as value
    o[max(temp)] = n

print(b(t,o[min(o)]))

```
> 4 votes

# Answer
# Python, 314 bytes

Many thanks to SP3000, grc, and FryAmTheEggman:

```
b=range;x=len
def p(i):
 l=[];z=''
 for n in t:
  if x(z)+x(n)<=i:z+=n+' '
  else:l+=[z];z=n+' '
 return l+[z]*(z!=l[x(l)-1])
t=input().split();q=[]
for i in b(70,91):l=p(i);q+=[max(sum(x(l[k+1])>j<x(l[k])and l[k][j]is' '==l[k+1][j]for k in b(x(l)-1))for j in b(i))]
print(*p(q.index(min(q))+70),sep='\n')

```
> 3 votes

# Answer
# JavaScript (ES6) 194 ~~202~~

Iterative solution, maybe shorter if made recursive

```
F=s=>{
  for(m=1e6,b=' ',n=70;n<91;n++)
    l=b+'x'.repeat(n),x=r=q='',
    (s+l).split(b).map(w=>
      (t=l,l+=b+w)[n]&&(
        l=w,r=r?[...t].map((c,p)=>x<(v=c>b?0:-~r[p])?x=v:v,q+=t+'\n'):[]
      )
    ),x<m&&(o=q,m=x);
  alert(o)
}

```

**Explained**

```
F=s=> {
  m = 1e9; // global max river length, start at high value
  for(n=70; n < 91; n++) // loop on line length
  {
    l=' '+'x'.repeat(n), // a too long first word, to force a split and start
    x=0, // current max river length
    q='', // current line splitted text
    r=0, // current river length for each column (start 0 to mark first loop)
    (s+l) // add a too long word to force a last split. Last and first row will not be managed
    .split(' ').map(w=> // repeat for each word
      (
        t=l, // current partial row in t (first one will be dropped)
        (l += ' '+w)[n] // add word to partial row and check if too long
        &&
        (
          l = w, // start a new partial row with current word
          r=r? // update array r if not at first loop
          (
            q+=t+'\n', // current row + newline added to complete text
            [...t].map((c,p)=>( // for each char c at position p in row t
              v = c != ' '
                ? 0 // if c is not space, reset river length at 0
                : -~r[p], // if c is space, increment river length
              x<v ? x=v : v // if current > max, update max
            ))
          ):[]
        )
      )
    )
    x < m && ( // if current max less than global max, save current text and current max
      o = q,
      m = x
    )
  }
  console.log(o,m)
}

```

**Test** in FireFox/FireBug console.

```
F('Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.')

```

*Output*

```
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis
nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore
eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt
in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor
sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut
labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis
aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in
culpa qui officia deserunt mollit anim id est laborum.

```
> 3 votes

# Answer
# Jelly, 37 bytes

```
Z=⁶ŒgẎ§Ṁ
KƤẈ>Tị⁸ðƬœ-ƝK€
ḲçⱮ70r90¤ÑÞḢY

```

Try it online!

## How it works

```
Z=⁶ŒgẎ§Ṁ - Link 1: Calculating max river length
         - Takes a list of lines on the left
Z        - Transpose
 =⁶      - Map spaces to 1 and everything else to 0
   Œg    - Over each row, group adjacent equal values
     Ẏ   - Tighten, removing the rows
      §  - Sum each
           The groups of adjacent elements are either runs of 0 or 1
           The sums map runs of 0s to 0, and runs of 1 to their lengths
       Ṁ - Yield the maximum

KƤẈ>Tị⁸ðƬœ-ƝK€ - Link 2: Breaks a string into a line width limited paragraph
               - Takes a list of words W on the left and a width N on the right
       ð       - Group into a dyad f(W, N):
 Ƥ             -   Over each prefix of W:
K              -     Join it by spaces
  Ẉ            -   Length of each
   >           -   Greater than N?
    T          -   Indices of truthy elements
     ị⁸        -   Index into W
                 This removes elements from W up the width N
        Ƭ      - Repeatedly apply f(W, N) until a fixed point
           Ɲ   - Over each overlapping pair [a, b]:
         œ-    -   Remove each element of b from a
            K€ - Join by spaces

ḲçⱮ70r90¤ÑÞḢY - Main link. Takes a string S on the left
Ḳ             - Split S into words, W
        ¤     - Create a nilad:
   70         -   70
      90      -   90
     r        -   Inclusive range; [70, 71, ..., 89, 90]
  Ɱ           - Over each element i in the range:
 ç            -   Call Link 2 with W on the left and i on the right
          Þ   - Sort by:
         Ñ    -   Max river length (Link 1)
           Ḣ  - First element (the narrowest width, and shortest river)
            Y - Join by newlines

```
> 2 votes

---
Tags: code-golf, string, whitespace, typography
---


title: Square root multiples

text:
# Question
Title: Square root multiples
This is based on OEIS sequence A261865.

> \\$A261865(n)\\$ is the least integer \\$k\\$ such that some multiple of \\$\sqrt{k}\\$ is in the interval \\$(n,n+1)\\$.

The goal of this challenge is to write a program that can find a value of \\$n\\$ that makes \\$A261865(n)\\$ as large as you can. A brute-force program can probably do okay, but there are other methods that you might use to do even better.

### Example

For example, \\$A261865(3) = 3\\$ because

* there is no multiple of \\$\sqrt{1}\\$ in \\$(3,4)\\$ (since \\$3 \sqrt{1} \leq 3\\$ and \\$4 \sqrt{1} \geq 4\\$);
* there is no multiple of \\$\sqrt{2}\\$ in \\$(3,4)\\$ (since \\$2 \sqrt{2} \leq 3\\$ and \\$3 \sqrt{2} \geq 4\\$);
* and there *is* a multiple of \\$\sqrt{3}\\$ in \\$(3,4)\\$, namely \\$2\sqrt{3} \approx 3.464\\$.

### Analysis

Large values in this sequence are rare!

* 70.7% of the values are \\$2\\$s,
* 16.9% of the values are \\$3\\$s,
* 5.5% of the values are \\$5\\$s,
* 2.8% of the values are \\$6\\$s,
* 1.5% of the values are \\$7\\$s,
* 0.8% of the values are \\$10\\$s, and
* 1.7% of the values are \\$\geq 11\\$.

### Challenge

The goal of this is to write a program that finds a value of \\$n\\$ that makes \\$A261865(n)\\$ as large as possible. Your program should run for no more than one minute and should output a number \\$n\\$. Your score is given by \\$A261865(n)\\$. In the case of a close call, I will run all entries on my 2017 MacBook Pro with 8GB of RAM to determine the winner.

For example, you program might output \\$A261865(257240414)=227\\$ for a score of 227. If two entries get the same score, whichever does it faster on my machine is the winner.

(Your program should not rely on information about pre-computed values, unless you can justify that information with a heuristic or a proof.)

# Answer
> 1 votes
# C++ (clang), score \\$399\\$

```
#include <iostream>
#include <cmath>
#include <vector>
#include <thread>

void f(unsigned long n)
{
    unsigned int m = 0;
    while (1) {
        unsigned long k = 1;
        while (++k) {
            const double sqrt_k = std::sqrt(static_cast<double>(k));
            const double x = sqrt_k * std::ceil(n/sqrt_k);
            if (n < x && x < n + 1) break;
        }
        if (k > m) {
            std::cout << "<" << k << "> for A261865(" << n << ")\n";
            m = k;
        }
        ++n;
    }
}

int main()
{
    const unsigned long block_size = 100000000000UL;
    const unsigned long num_threads = 12;
    std::vector<unsigned int> results(num_threads);
    std::vector<std::thread> threads(num_threads - 1);
    unsigned long start = 1UL;
    for (int i = 0; i < num_threads - 1; ++i) {
        threads[i] = std::thread(f, start);
        start += block_size;
    }
    for (auto& entry: threads) {
        entry.join();
    }
}

```

Try it online!

Gets \\$313\\$ on TIO.
Gets \\$399\\$ on my laptop (Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz with 16 GB RAM):

```
#include <iostream>
#include <cmath>
#include <sys/time.h>
#include <vector>
#include <thread>

int sigTimerSet(int seconds)
{
    std::cout << "Starting timer for " << seconds << " seconds.\n";

    struct itimerval old_one, new_one;
    new_one.it_interval.tv_usec = 0;
    new_one.it_interval.tv_sec = 0;
    new_one.it_value.tv_usec = 0;
    new_one.it_value.tv_sec = static_cast<long int>(seconds);
    if (setitimer (ITIMER_REAL, &new_one, &old_one) < 0)
        return 0;
    else
        return old_one.it_value.tv_sec;
}

void f(unsigned long n)
{
    unsigned int m = 0;
    while (1) {
        unsigned long k = 1;
        while (++k) {
            const double sqrt_k = std::sqrt(static_cast<double>(k));
            const double x = sqrt_k * std::ceil(n/sqrt_k);
            if (n < x && x < n + 1) break;
        }
        if (k > m) {
            std::cout << "<" << k << "> for A261865(" << n << ")\n";
            m = k;
        }
        ++n;
    }
}

int main()
{
    sigTimerSet(60);

    const unsigned long block_size = 100000000000UL;
    const unsigned long num_threads = std::thread::hardware_concurrency();
    std::vector<unsigned int> results(num_threads);
    std::vector<std::thread> threads(num_threads - 1);
    unsigned long start = 1UL;
    for (int i = 0; i < num_threads - 1; ++i) {
        threads[i] = std::thread(f, start);
        start += block_size;
    }
    for (auto& entry: threads) {
        entry.join();
    }
}

```

produces:

```
Starting timer for 60 seconds.
<2> for A261865(1)
<3> for A261865(3)
<7> for A261865(23)
<15> for A261865(30)
<38> for A261865(184)
<3> for A261865(200000000001)
<2> for A261865(300000000001)
<3> for A261865(300000000003)
<<2> for A261865(60000000000143)
<<5> for A261865(3000000000065)
<<6> for A261865(300000000016)
<14> for A261865(300000000023)
<15> for A261865(300000000115)
<19> for A261865(300000000160)
<21> for A261865(300000000399)
<26> for A261865(300000000716)
<2> for A261865(400000000001)
<5> for A261865(400000000002)
<6> for A261865(400000000032)
<11> for A261865(400000000039)
<14> for A261865(400000000063)
<53> for A261865(400000000316)
<3> for A261865(600000000003)
<5> for A261865(600000000006)
<6> for A261865(600000000016)
<295> for A261865(400000002890)
<2> for A261865(900000000001)
<6> for A261865(900000000003)
<10> for A261865(900000000037)
<17> for A261865(900000000108)
<19> for A261865(900000000320)
<30> for A261865(900000000522)
<31> for A261865(900000001146)
<2> for A261865(800000000001)
<5> for A261865(800000000004)
<6> for A261865(800000000034)
<11> for A261865(800000000072)
<<39> for A261865(900000003574)
<35> for A261865(800000000079)
38<<> for A261865(300000002673)
> for A261865(<2> for A261865(100000000001)
<5> for A261865(100000000002)
> for A261865(<13> for A261865(100000000009)
<21> for A261865(100000000340)
<> for A261865(<29> for A261865(100000001644)
77> for A261865(<> for A261865(600000000027)
<10> for A261865(600000000037)
<15> for A261865(600000000068)
<21> for A261865(600000000139)
8091)
51> for A261865(900000008337)
<13> for A261865(1000000000001)
<15> for A261865(1000000000018)
<23> for A261865(1000000000124)
<46> for A261865(16060)
<<29> for A261865(1000000002029)
<38> for A261865(1000000002313)
200000000004)
<10> for A261865(200000000014)
<11> for A261865(200000000028)
<13> for A261865(200000000383)
<17> for A261865(200000000584)
<23> for A261865(200000000861)
71<46> for A261865(200000001329)
42> for A261865(300000003489)
<58> for A261865(200000003435)
<53> for A261865(300000004909)
<<62> for A261865(200000006771)
<30> for A261865(100000003880)
<37> for A261865(100000004041)
> for A261865(<38> for A261865(100000004980)
<<39> for A261865(100000005673)
700000000001)
<51> for A261865(100000008489)
<10> for A261865(700000000063)
<15> for A261865(700000000077)
<19> for A261865(700000000264)
500000000001<26> for A261865(700000001087)
39<30> for A261865(700000001941)
<<38> for A261865(700000002098)
800000005135<43> for A261865(700000002630)
29> for A261865(600000001409)
> for A261865()
<<5> for A261865(500000000004)
31> for A261865(600000003011)
)
1000000003259)
<42> for A261865(1000000005365)
<62> for A261865(300000022786)
<73> for A261865(700000007516)
<35> for A261865(600000003458)
<53> for A261865(1000000014642)
<58> for A261865(16907)
<67> for A261865(600000006910)
<55> for A261865(100000020333)
<79> for A261865(200000057626)
<21> for A261865(500000000018)
<<23> for A261865(500000001052)
<<33> for A261865(500000001414)
<35> for A261865(500000001568)
<<70> for A261865(300000025183)
62> for A261865(100000024519)
61> for A261865(20993)
65> for A261865(1000000025765)
85<74> for A261865(100000027954)
<97> for A261865(26286)
> for A261865(900000026060)
<66> for A261865(1000000037855)
<79> for A261865(100000035523)
<85> for A261865(200000088176)
<93> for A261865(900000037207)
<97> for A261865(300000061052)
<79> for A261865(600000074122)
<78> for A261865(800000098681)
<122> for A261865(400000213561)
<79> for A261865(700000110055)
<101> for A261865(900000115082)
<118> for A261865(130375)
<95> for A261865(600000136687)
<85> for A261865(700000175977)
<127> for A261865(169819)
<74> for A261865(1000000208668)
<95> for A261865(200000283049)
<95> for A261865(100000278291)
<79> for A261865(800000325129)
<83> for A261865(800000382758)
<101> for A261865(300000348034)
<82> for A261865(1000000377945)
<113> for A261865(600000368089)
<115> for A261865(600000388325)
<114> for A261865(900000458149)
<94> for A261865(800000523290)
<57> for A261865(500000002957)
<91> for A261865(500000020356)
<94> for A261865(500000086735)
<123> for A261865(1000000615915)
<139> for A261865(900000597046)
<113> for A261865(700000641956)
<122> for A261865(500000189745)
<138> for A261865(500000344679)
<109> for A261865(300000963142)
<129> for A261865(600001013758)
<139> for A261865(400001233496)
<177> for A261865(300001283249)
<107> for A261865(800001360974)
<110> for A261865(100001440670)
<119> for A261865(200001950373)
<127> for A261865(200002180270)
<119> for A261865(100001936762)
<130> for A261865(2135662)
<123> for A261865(700002323159)
<146> for A261865(600001831667)
<187> for A261865(2345213)
<109> for A261865(800002595588)
<145> for A261865(700002807851)
<155> for A261865(500003070679)
<194> for A261865(300003944386)
<127> for A261865(1000003765582)
<142> for A261865(1000003972101)
<165> for A261865(100003914551)
<110> for A261865(800004935331)
<141> for A261865(200005383478)
<186> for A261865(800005847131)
<157> for A261865(600005644046)
<185> for A261865(200006038768)
<178> for A261865(400008172024)
<183> for A261865(500008457011)
<163> for A261865(1000010164463)
<190> for A261865(800013713435)
<146> for A261865(900015388529)
<197> for A261865(600016805653)
<155> for A261865(700016980104)
<165> for A261865(1000017298685)
<185> for A261865(1000023033133)
<186> for A261865(100022787204)
<157> for A261865(700023653342)
<161> for A261865(700024255285)
<159> for A261865(900023644405)
<202> for A261865(900027523835)
<303> for A261865(700033230641)
<199> for A261865(300035412403)
<215> for A261865(500035617384)
<195> for A261865(800035729684)
<223> for A261865(600037942250)
<193> for A261865(46272966)
<221> for A261865(500060347857)
<197> for A261865(100072149460)
<226> for A261865(200071020948)
<219> for A261865(800096272342)
<273> for A261865(100096408342)
<195> for A261865(1000138255835)
<313> for A261865(600147859274)
<210> for A261865(300158020199)
<305> for A261865(300163012534)
<179> for A261865(400173203199)
<249> for A261865(500185649969)
<281> for A261865(900217000298)
<210> for A261865(222125822)
<222> for A261865(1000221604207)
<217> for A261865(237941698)
<227> for A261865(257240414)
<229> for A261865(1000299563639)
<191> for A261865(400330753112)
<237> for A261865(800371022066)
<197> for A261865(400388377102)
<222> for A261865(400519662337)
<247> for A261865(1000659372263)
<251> for A261865(400686850499)
<293> for A261865(900791054060)
<258> for A261865(201101992489)
<267> for A261865(1205703469)
<255> for A261865(501227521557)
<258> for A261865(501233713968)
<399> for A261865(1001313673399)
<299> for A261865(1558293414)
<271> for A261865(801556690220)
<286> for A261865(501665988151)
<257> for A261865(401963829763)
<357> for A261865(901991228083)
<290> for A261865(101979205483)
<293> for A261865(102084473850)
<282> for A261865(402539565301)
Alarm clock

```

Note the **\<399\> for A261865(1001313673399)**! :D

# Answer
> 4 votes
# C (gcc), Score 335 on TIO

```
#include <stdio.h>
#include <math.h>

int main() {

    double n = 0, k;

    while( n += 13 ) {

        for(k = 2; ceil(sqrt((n + 1) * (n + 1) / k)) - floor(sqrt(n * n / k)) < 2; k++);

        if( k > 250 ) printf("%.lf -> %.lf\n", n, k);
    }

    return 0;
}

```

Try it online!

The algorithm to compute A(n) is took from the OEIS page.

The `n` for which A(n) is being computed, follows the heuristics below:

I computed these first few A(n) greater than 100

```
   n    -> A(n)  | Factors of n
-------------------------------
 130375 -> 118   | 5 5 5 7 149
 169819 -> 127   | 13 13063
 902236 -> 103   | 2 2 211 1069
1227105 -> 106   | 3 3 5 11 37 67
1793759 -> 105   | 11 179 911
1940874 -> 103   | 2 3 13 149 167
1962875 -> 105   | 5 5 5 41 383
2135662 -> 130   | 2 1067831
2345213 -> 187   | 13 13 13877
2470326 -> 111   | 2 3 411721
3461537 -> 115   | 3461537
4221630 -> 105   | 2 3 3 5 7 6701
4576794 -> 103   | 2 3 229 3331
5021205 -> 114   | 3 5 7 17 29 97
5396362 -> 110   | 2 2698181
8567238 -> 102   | 2 3 29 53 929
9182575 -> 103   | 5 5 89 4127
9983754 -> 102   | 2 3 3 11 50423

```

Where there are two notable local maximum: **127** and **187**.

As you can see, in both cases the generating `n` is a multiple of **13**, and that seemed to me a good enough reason to conjecture that, on average, multiples of 13 may generate an higher A(n) than most numbers of the same magnitude.

So I made a program to compute the multiples of 13 and leaving it running for a minute on TIO, the maximum I get is

```
11145613453 -> 335

```

# Answer
> 3 votes
# JavaScript (Node.js), score \\$335\\$

Pretty straight-forward algorithm. I made it multithreaded to be a bit faster.

```
// Run with: node ./square-root-multiples.js

const findMaxK = (fromN, toN) => {
  let maxK = 0;
  let maxN = 0;
  for (let n = fromN; n < toN; n++) {
    for (let k = 2, s = n * n; k < s; k++) {
      const r = Math.sqrt(k);
      const x = r * Math.ceil(n / r);
      if (x > n && x < n + 1) {
        if (k > maxK) {
          maxK = k;
          maxN = n;
        }
        break;
      }
    }
  }
  return { n: maxN, k: maxK };
};

const BATCH_SIZE = 10000000;

const cluster = require("cluster");
if (cluster.isMaster) {
  const start = Date.now();
  let nextBatch = 0;
  let maxK = 0;

  const numCpus = require("os").cpus().length;
  for (let i = 0; i < numCpus; i++) {
    const worker = cluster.fork();
    worker.on("message", (msg) => {
      if (msg.k > maxK) {
        maxK = msg.k;
        console.log(
          `found A261865(${msg.n}) = ${msg.k} in ${
            (Date.now() - start) / 1000
          }s`
        );
      }
      worker.send({ n: nextBatch, maxK });
      nextBatch += BATCH_SIZE;
    });
    worker.send({ n: nextBatch });
    nextBatch += BATCH_SIZE;
  }
} else {
  process.on("message", (msg) => {
    process.send(findMaxK(msg.n, msg.n + BATCH_SIZE));
  });
}

```

Output on my 2019 MacBook Pro:

```
found A261865(12779527) = 134 in 0.299s
found A261865(2345213) = 187 in 0.308s
found A261865(63856063) = 193 in 0.33s
found A261865(222125822) = 210 in 0.681s
found A261865(237941698) = 217 in 0.687s
found A261865(257240414) = 227 in 0.804s
found A261865(1217775885) = 230 in 2.704s
found A261865(1205703469) = 267 in 2.704s
found A261865(1558293414) = 299 in 3.306s
found A261865(4641799364) = 303 in 13.002s
found A261865(6600656102) = 323 in 20.045s
found A261865(11145613453) = 335 in 36.774s
found A261865(20641456345) = 354 in 73.047s

```

The highest K my machine found within 60s was `A261865(11145613453) = 335`.

# Answer
> 3 votes
# C (clang), score 210 on TIO

```
#include <stdio.h>
int main() {
 unsigned long long x, i, j, k;
 for (x = 2; x < 222125823ULL; x++) {
  for (i = 1; ; i++) {
   for (j = 2; j * j * i <= x * x; j *= 2);
   for (k = j / 2; k /= 2; ) if ((j - k) * (j - k) * i > x * x) j -= k;
   if (j * j * i < (x + 1) * (x + 1)) break;
  }
  if (i > 99) {
   printf("A261865(%llu)=%llu\n", x, i);
   fflush(stdout);
  }
 }
}

```

Try it online! Calculates all A261865 entries from 2 to 222,125,822 in just under 60s on TIO. Annoyingly, it doesn't seem to be possible to reach 250,000,000 within the time limit. In any case it is limited to about 2,000,000,000 due to the use of 64-bit integer arithmetic (no square root operations). By switching to `unsigned __int128` you could quickly calculate A261865 for specific higher values of course.

Edit: Just tried a threaded version on my local 16-core processor and it can reach 2,000,000,000 in just under 60 seconds, finding A261865(1558293414)=299. Soon after that it stops working because j reaches 4,294,967,296 and then j * j overflows to zero.

Edit: I left the 128-bit single-threaded version running overnight and it found the following record values for A261865:

```
A261865(3)=3 (0s)
A261865(23)=7 (0s)
A261865(30)=15 (0s)
A261865(184)=38 (0s)
A261865(8091)=43 (0s)
A261865(16060)=46 (0s)
A261865(16907)=58 (0s)
A261865(20993)=61 (0s)
A261865(26286)=97 (0s)
A261865(130375)=118 (0s)
A261865(169819)=127 (0s)
A261865(2135662)=130 (0.7s)
A261865(2345213)=187 (0.8s)
A261865(46272966)=193 (17.8s)
A261865(222125822)=210 (91.7s)
A261865(237941698)=217 (98.6s)
A261865(257240414)=227 (1.8m)
A261865(1205703469)=267 (8.9m)
A261865(1558293414)=299 (11.6m)
A261865(4641799364)=303 (34.9m)
A261865(6600656102)=323 (49.9m)
A261865(11145613453)=335 (85m)
A261865(20641456345)=354 (2.7h)
A261865(47964301877)=358 (6.3h)
A261865(105991039757)=385 (14.2h)
A261865(119034690206)=397 (16h)
A261865(734197670805)=455 (4.4d)

```

# Answer
> 3 votes
# C (gcc), A261865(6600656102)=323 on TIO

This out this checks every `A(n)` sequentially (well, based on the small `CHUNKSIZE`, and it skips a lot of values based on optimization, see the How it works).

```
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>

//#define L unsigned __int128
//#define F __float128
#define L unsigned long long
#define F long double
#define MAXN (1024ull*1024ull*1024ull*1024ull)
#define CHUNKSIZE (1024ull*1024ull)
#define CHECKS 8
#define BUFFER 1024

int main() {
 F steps[CHECKS + BUFFER], values[CHECKS + BUFFER];
 steps[0] = sqrtl(2) / (sqrtl(2) - 1);
 steps[1] = sqrtl(3) / (sqrtl(3) - 1);
 int n=5, min_check;
 for (int i = 2; i < CHECKS + BUFFER; n++) {
  int ok = 1;
  for (int tmp = 2; tmp < sqrtl(n) + 0.5; tmp++)
   if (n % (tmp * tmp) == 0) ok = 0;
  if (!ok)
   continue;
  values[i] = n;
  steps[i++] = sqrtl(n);
  if (i == CHECKS) min_check = i;
 }

 char chunk[CHUNKSIZE] = { 0 };

#pragma omp parallel for private(chunk) schedule(static, 1)
 for (L chunki = 0; chunki < (MAXN / CHUNKSIZE); chunki++) {

  L start = chunki * CHUNKSIZE, end = (chunki + 1) * CHUNKSIZE;

  for (L i = start / steps[1] + 1; i < end / steps[1]; i++)
   chunk[(L)(i * steps[1]) - start] = 1;
  for (int k = 2; k < CHECKS; k++)
   for (L i = start / steps[k] + 1; i < end / steps[k]; i++)
    chunk[(L)(i * steps[k]) - start] = 0;

  for (L i = start / steps[0] + 1; i < end / steps[0]; i++) {
   L xi = (L)(i * steps[0]) - start;
   if (chunk[xi] == 1) {
    chunk[xi] = 0;
    L x = xi + start;
    int k = min_check;
    while (++k) {
     F sqrt_k = steps[k];
     F try = sqrt_k * ceill(x/sqrt_k);
     if (x < try && try < x + 1) break;
    }
    k = values[k];
    if (k > 249)
     printf("A261865(%llu)=%d\n", x, k), fflush(stdout);
   }
  }
 }
}

```

Try it online!

### How it works

We sieve through the numbers: `floor(i * sqrt(n))` is a Beatty sequence. The nice thing about these is that their complement is easy to calculate. So if `floor(i * sqrt(2))` hits `1 2 4 5 7 8 9 …`, `floor(i * (sqrt(2) / (sqrt(2) - 1)))` hits `3 6 10 13 17 20 23 …` This alone saves us about two third calculation time.

For `n>4`, `sqrt(n)` is actually bigger than `(sqrt(2) / (sqrt(2) - 1)`. So we initialize an array of 0s, set every non-multiple of `sqrt(3)` to 1, and for every `n` between 3 and `CHECKS` we set every multiple of `sqrt(n)` back to 0. We then take the big steps of `(sqrt(2) / (sqrt(2) - 1)` and if there the array is set to 1, we know that `A(i)` is at least `CHECKS`.

`A(n)` must be a square free number, as the square of its square divisor (8 -\> 4 -\> 2) will already have hit the same numbers, so we can skip `4 8 9 12 16 …`, too.

The actual computation of `A(n)` is borrowed from @Noodle9. But we can start with `i = CHECKS`.

Bundled all of this with OpenMP for easy multithreading for the chunks and some performance testing to get a good value for `CHECKS`, we get to 383 on TIO. If you want to get further than `A(2^64)`, you need to define `L` and `F` to `unsigned __int128` and `__float128`.

# Answer
> 3 votes
# C (clang), score 299 on TIO

```
#include <stdio.h>
#define A261865 256
unsigned long long J[A261865], K[A261865];
int main() {
 int i, m;
 unsigned long long x, j, k;
 for (i = 1; i < A261865; i++) J[i] = K[i] = i;
 m = 2;
 for (x = 1; x < 0x60000000ULL; x++) {
  for (i = 1; ; i++) {
   if (i < A261865) {
    while (J[i] <= x * x) J[i] += K[i] += i + i;
    if (J[i] < (x + 1) * (x + 1)) break;
   } else {
    for (j = k = i; j <= x * x; j += k += i + i);
    if (j < (x + 1) * (x + 1)) break;
   }
  }
  if (i > m) {
   printf("A261865(%llu)=%d\n", x, i);
   fflush(stdout);
   m = i;
  }
 }
}

```

Try it online! Takes under 60s to output:

```
A261865(3)=3
A261865(23)=7
A261865(30)=15
A261865(184)=38
A261865(8091)=43
A261865(16060)=46
A261865(16907)=58
A261865(20993)=61
A261865(26286)=97
A261865(130375)=118
A261865(169819)=127
A261865(2135662)=130
A261865(2345213)=187
A261865(46272966)=193
A261865(222125822)=210
A261865(237941698)=217
A261865(257240414)=227
A261865(1205703469)=267
A261865(1558293414)=299

```

Using a version with a 128-bit integer type and larger square root cache, this code has found the following values on my PC:

```
A261865(3)=3 (0s)
A261865(23)=7 (0s)
A261865(30)=15 (0s)
A261865(184)=38 (0s)
A261865(8091)=43 (0s)
A261865(16060)=46 (0s)
A261865(16907)=58 (0s)
A261865(20993)=61 (0s)
A261865(26286)=97 (0s)
A261865(130375)=118 (0s)
A261865(169819)=127 (0s)
A261865(2135662)=130 (0s)
A261865(2345213)=187 (0s)
A261865(46272966)=193 (1s)
A261865(222125822)=210 (5.2s)
A261865(237941698)=217 (5.7s)
A261865(257240414)=227 (6.2s)
A261865(1205703469)=267 (31s)
A261865(1558293414)=299 (41.8s)
A261865(4641799364)=303 (2.1m)
A261865(6600656102)=323 (3m)
A261865(11145613453)=335 (5.2m)
A261865(20641456345)=354 (9.8m)
A261865(47964301877)=358 (22.9m)
A261865(105991039757)=385 (52m)
A261865(119034690206)=397 (59.1m)
A261865(734197670865)=455 (6.4h)
A261865(931392113477)=501 (8.4h)
A261865(1560674332481)=505 (14.2h)

```

It also found `A261865(5928861186373)=509`, but I wasn't able to run it continuously for the ~2 days needed, so I don't know how long it took.

# Answer
> 2 votes
# Python 3, score \\$193\\$

```
from math import ceil, floor, sqrt

def f(n):
    k = 2
    while ceil(sqrt((n + 1)**2/k)) - floor(sqrt(n**2/k)) < 2:
        k += 1
    return k

```

Try it online!

Straight forward port of the Mathematica code on OEIS A261865 to get the ball rolling.

On my laptop (Intel(R) Core(TM) i7-8750H CPU @ 2.20 GHz with 16 GB RAM):

```
from functools import wraps
import errno
import os
import signal

class TimeoutError(Exception):
    pass

def timeout(seconds=10, error_message=os.strerror(errno.ETIME)):
    def decorator(func):
        def _handle_timeout(signum, frame):
            raise TimeoutError(error_message)

        def wrapper(*args, **kwargs):
            signal.signal(signal.SIGALRM, _handle_timeout)
            signal.alarm(seconds)
            try:
                result = func(*args, **kwargs)
            finally:
                signal.alarm(0)
            return result

        return wraps(func)(wrapper)

    return decorator

from math import ceil, floor, sqrt

@timeout(60)
def f():
    n = 1
    m = 1
    while 1:
        k = 2
        while ceil(sqrt((n + 1)**2/k)) - floor(sqrt(n**2/k)) < 2:
            k += 1
        if k > m:
            print(f'A({n}) -> {k}')
            m = k
        n += 1
f()

```

produces:

```
A(1) -> 2
A(3) -> 3
A(23) -> 7
A(30) -> 15
A(184) -> 38
A(8091) -> 43
A(16060) -> 46
A(16907) -> 58
A(20993) -> 61
A(26286) -> 97
A(130375) -> 118
A(169819) -> 127
A(2135662) -> 130
A(2345213) -> 187
A(46272966) -> 193
Traceback (most recent call last):
  File "A261865_timeout.py", line 41, in <module>
    f()
  File "A261865_timeout.py", line 18, in wrapper
    result = func(*args, **kwargs)
  File "A261865_timeout.py", line 35, in f
    while ceil(sqrt((n + 1)**2/k)) - floor(sqrt(n**2/k)) < 2:
  File "A261865_timeout.py", line 12, in _handle_timeout
    raise TimeoutError(error_message)
__main__.TimeoutError: Timer expired

```

---
Tags: math, code-challenge, sequence, number-theory, optimized-output
---


title: Is it a vampire number?

text:
# Question
Title: Is it a vampire number?
Repost and improvement of this challenge from 2011

A vampire number is a positive integer \\$v\\$ with an even number of digits that can be split into 2 smaller integers \\$x, y\\$ consisting of the digits of \\$v\\$ such that \\$v = xy\\$. For example:

$$1260 = 21 \times 60$$

so \\$1260\\$ is a vampire number. Note that the digits for \\$v\\$ can be in any order, and must be repeated for repeated digits, when splitting into \\$x\\$ and \\$y\\$. \\$x\\$ and \\$y\\$ must have the same number of digits, and only one can have trailing zeros (so \\$153000\\$ is not a vampire number, despite \\$153000 = 300 \times 510\\$).

You are to take a positive integer \\$v\\$ which has an even number of digits and output whether it is a vampire number or not. You can either output:

* Two consistent, distinct values
* A (not necessarily consistent) truthy value and a falsey value
    + For example, "a positive integer for true, 0 for false"

You may input and output in any convenient method. This is , so the shortest code in bytes wins.

The first 15 vampire numbers are \\$1260, 1395, 1435, 1530, 1827, 2187, 6880, 102510, 104260, 105210, 105264, 105750, 108135, 110758, 115672\\$. This is sequence A014575 on OEIS. **Be sure to double check that your solution checks for trailing zeros; \\$153000\\$ should return false.**

# Answer
# Husk, ~~18~~ ~~17~~ ~~14~~ ~~13~~ 12 bytes

*Edit: -3 bytes, and then another -1 byte, thanks to Leo, and -1 byte thanks to inspiration from pajonk's R answer (3rd edit)*

```
€¹mΠ†dm½f→Pd

```

Try it online!

Outputs nonzero integer if it's a vampire number, zero otherwise.

Commented penultimate version:

```
€¹                  # index of input if present, zero otherwise, in
  mΠ                # products of each element-pair
    †d              # combining digits as a number from
         m½         # first & second halves of
           P        # all permutations of
            d       # digits of input;
      f             # and filtering only element-pairs for which
       ṁ→           # sum of last digits is nonzero

```
> 8 votes

# Answer
# , ~~156~~ ~~146~~ ~~143~~ 135 bytes

*-10 bytes thanks to Dominic van Essen*

```
function(n,s=strsplit){for(i in 1:n)if(!n%%i&nchar(j<-n/i)==nchar(i)&all(el(s(paste0(j,i),''))%in%el(s(c(n,''),'')))&i%%10)return(T)
F}

```

Try it online!
> 7 votes

# Answer
# , 43 bytes

```
".e.-@-:@#((0<[:".{:\)*[:*/".\)"1 i.@!@#A.]

```

Try it online!

Takes digits as a string.

For each permutation `i.@!@#A.]`, use half the digit length `-@-:@#` to take non-overlapping infixes -- which slices into 2 halves -- and multiply those halves`([:*/".\)"1`. Then (to handle the trailing zero constraint) multiply *that* by `(0<[:".{:\)*`, which takes the last digits of each half, cats them, evaluates that as a two digit number, and checks if it's greater than 0.

Finally, check if the input number `".` is an element of that list `e.`.
> 6 votes

# Answer
# JavaScript (Node.js), 88 bytes

```
f=(n,i=1)=>n<i*i*10&&i%10&&[...''+i+n/i].sort()+''==[...''+n].sort()||n*10>++i*i&&f(n,i)

```

Try it online!

* `[...''+i+n/i].sort()+''==[...''+n].sort()` two factors use and only use digits in original number
    + if `n/i` is not an integer, it converted into a string with `.` and not equals to another side which doesn't contain a `.`.
* `n<i*i*10`, `n*10>i*i`: lengths of two numbers are the same.
    + It equip to `i/10 < n/i < i*10`. And since `n` has even number of digits (as question mentioned), `i` and `n/i` will have same number of digits.
* `i%10`: `i` is not end with "0"
> 6 votes

# Answer
# C (gcc), ~~286~~ ~~240~~ 218 bloody bytes (o,\_,o)

-55 bloody bytes thanks to ceilingcat!

```
#define S(x,y)x^=y^=x^=y
o,a,b,c,r;f(int*_){c=atoi(_);v(o,_,o=strlen(_),r=0);r=r;}v(k,_,o,i)char*_;{--k?({for(v(k,_,o,0);i<k;v(k,_,o,!++i))S(_[k%2*i],_[k]);}):(a=atoi(_)/exp10(o/2))*(b=atoi(_+o/2))==c&&(a+b)%10?r=1:0;}

```

Try it online!

The input is a string and the output is either 1 or 0.

The core of the answer is the function `v()`, which implements Heap's algorithm to generate all the possible permutations of the input digits.

Here's an explanation of the code before some golfing:

```
#define S(x,y)x^=y^=x^=y                 // Macro used to swap digits
o,                                       // length of the input string
a,                                       // first half of one of the possible permutations of digits
b,                                       // second half
r;                                       // result: 1 if the input is a vampire number, 0 otherwise
char c[9];                               // copy of the original input that will be compared with the permutations
f(_)char*_;{                             // That's a simple function taking the input string
    r=!strcpy(c,_);                      // initializing `r` to 0 and `c` to the input
    v(o,_,o=strlen(_));                  // calling v(o,_,o) while initializing `o` to the length of the input
    r=r;                                 // and returning rhe result `r`
}
v(                                       // v() is a recursive function taking three parameters:
k,                                       // the length of a substring of digits being permuted
_,                                       // the whole current permutation
o,                                       // the length of the whole permutation
i)                                       // `i` is here just to avoid declaring `int i` inside the `for` loop
char*_;{
    if(k-1){                             // if `k` is not 1
        v(k-1,_,o);                      // call v() to permute `k-1` digits
        for(i=0;++i<k;                   // until `i` is less than `k`
        v(k-1,_,o))                      // call v() to permute `k-1` digit, but only after having
            S(_[k%2?0:i-1],_[k-1]);      // swapped _[k-1] with either _[0] or _[i-1]
    }
    else                                 // else (i.e. if k == 1)
        (a=atoi(_)/exp10(o/2))           // if `a` (getting the first half of the permutation, converted to integer)
        *(b=atoi(_+o/2))                 // multiplied by `b` (getting the second half)
        ==atoi(c)                        // equals the original input
        &&(a+b)%10?                      // and only one between `a` and `b` has trailing zeros
        r=1                              // then the result is set to 1
        :0;                              // otherwise do nothing, this permutation wasn't the right one
}

```

I tried other algorithms, but couldn't find a shorter one. I leave here the dumbest of the tries, which is a solution that doesn't solve the problem. It only finds most of the vampire numbers (probably).
> 5 votes

# Answer
# 05AB1E, 14 bytes

```
œ2δäÅΔPQy€θĀà*

```

Outputs a non-negative integer as truthy and `-1` as falsey.

Try it online or verify all test cases.

**Explanation:**

```
œ            # Get all permutations of the (implicit) input
  δ          # Map over each permutation:
 2 ä         #  And split it into two equal-sized halves
    ÅΔ       # Get the 0-based index of the first truthy result,
             # or -1 if none are found:
      P      #  Take the product of the two halves
       Q     #  And check that it's equal to the (implicit) input
      y      #  Push the halves again
       €θ    #  Only leave the last digit of each halve
         Ā   #  Check that it's not 0 (1 if [1-9]; 0 if 0)
          à  #  Get the maximum of these two
      *      #  Multiply the checks to verify both are truthy
             #  (after which the found index is output implicitly as result)

```
> 5 votes

# Answer
# Python 2, ~~113 ... 112~~ 109 bytes

```
def f(n,s=sorted):x=s(`n`);l=10**(len(x)/2);return any(x==s(`i`+`n/i`)for i in range(l/10,l)if i%10and n%i<1)

```

Try it online!

-3 byte thanks Kevin Cruijssen
> 4 votes

# Answer
# Python 2, ~~105~~ ~~95~~ 94 bytes

-10 bytes thanks to Kevin Cruijssen! (switch to Python 2)
-1 byte thanks to dingledooper!

Very inefficient, segfaults for \\$ n \gtrsim 18500\\$ on TIO.

```
f=lambda n,k=2,S=sorted:k<n and(k%10>n%k<(len(`k`)==len(`n/k`)<S(`k`+`n/k`)==S(`n`)))|f(n,k+1)

```

Try it online!

**Commented**:

```
f=lambda n,k=2,S=sorted   # recursive function
  k<n                     # if k>=n return False
  and                     # otherwise:
  ( ... )                 # long boolean expression which is True if k and n//k make n a valid vampire number
    k%10                  # the last digit of k is
  > n%k                   # larger than n%k which is
  < ( ... )               # less than another boolean expression
                          # These two comparisons can only be satisfied with k%10>0<1
      len(`k`)            # the number of digits of k
   == len(`n/k`)          # is equal to the number of digits of n//k
    < S(`k`+`n/k`)        # and sorting the digits of k and n//k
   == S(`n`)              # results in the same list as sorting the digits of n

| f(n,k+1)                # bitwise OR with result of the recursive call

```
> 4 votes

# Answer
# Charcoal, 54 bytes

```
⊞υ⟦ωθ⟧ＦυＦＥ§ι¹⟦⁺§ι⁰κΦ§ι¹⁻λν⟧⊞υκ⊙ＥΦυ¬⊟ιＩ⪪⊟ι⊘Ｌθ∧Σ﹪ιχ⁼θＩΠι

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for vampire, nothing if not. Explanation:

```
⊞υ⟦ωθ⟧

```

Start a breadth-first enumeration of permutations of the input string.

```
Ｆυ

```

Loop over each partial permutation so far.

```
ＦＥ§ι¹⟦⁺§ι⁰κΦ§ι¹⁻λν⟧⊞υκ

```

Append each unused character to the permutation so far and push the result plus the remaining characters to the list.

```
⊙ＥΦυ¬⊟ι

```

Find whether any of the entries where all of the characters were used, ...

```
Ｉ⪪⊟ι⊘Ｌθ

```

... after being split into halves and cast to integer, ...

```
∧Σ﹪ιχ

```

... have a non-zero sum of the last digits, ...

```
⁼θＩΠι

```

... and have the product of the halves resulting in the original string.
> 4 votes

# Answer
# Ruby, ~~104~~ 96 bytes

It almost looks like a complete English sentence. Which probably is a bad thing for golfing.

```
->n{n.digits.permutation.any?{|s|a,b=s.each_slice(s.size/2).map{|x|x.join.to_i};a%10>0&&a*b==n}}

```

Try it online!

It can be written in 94 bytes with Ruby 2.7:

```
->n{n.digits.permutation.any?{|s|a,b=s.each_slice(s.size/2).map{_1.join.to_i};a%10>0&&a*b==n}}

```
> 4 votes

# Answer
# JavaScript (ES6), 93 bytes

Assumes that the input has an even number of digits. Returns a Boolean value.

```
f=(n,[...a]=n,p='')=>a[p.length]?a.some((v,i)=>f(n,a.filter(_=>i--),p+v)):p%10&&p*a.join``==n

```

Try it online!

---

# JavaScript (ES6), 97 bytes

Expects the integer as a string. Returns **0** or **1**.

```
f=(n,[...a]=n,p,q,k)=>a.some((v,i)=>f(n,a.filter(_=>i--),k?[p]+v:p,k?q:[q]+v,!k))|p%10*!(p*q^n|k)

```

Try it online!

### Commented

```
f = (                     // f is a recursive function taking:
  n,                      //   n = input integer, as a string
  [...a] = n,             //   a[] = list of digits of n
  p, q,                   //   n is split into p and q (both initially undefined)
  k                       //   k is a flag, set on odd iterations
) =>                      //
  a.some((v, i) =>        // for each digit v at position i in a[]:
    f(                    //   do a recursive call:
      n,                  //     pass n unchanged
      a.filter(_ => i--), //     remove the i-th entry from a[]
      k ? [p] + v : p,    //     append v to p if k is set
      k ? q : [q] + v,    //     append v to q if k is not set
      !k                  //     toggle k
    )                     //   end of recursive call
  )                       // end of some()
  |                       // success if:
    p % 10 *              //   the last digit of p is not 0,
    !(p * q ^ n | k)      //   p * q = n and k is not set

```
> 3 votes

# Answer
# Jelly, 15 bytes

```
Œ!ŒH€SṪ$ƇḌP€=ḌẸ

```

Try it online!

Takes a list of digits.
> 2 votes

# Answer
# Japt, 20 bytes

```
á mó f_dÌÃ®mì ×Ãd¥Uì

```

Try it online! or check all test cases (specifically the 15 vampire numbers and 153000)

Takes input as an array of digits. Input as an integer is one byte longer

Explanation:

```
á mó f_dÌÃ®mì ×Ãd¥Uì
á                       # Get all permutations of the input digits
  mó                    # Divide each permutation into two groups of equal length
     f_  Ã              # Only keep ones where:
       dÌ               #  At least one of the groups ends with a non-zero number
          ®    Ã        # For each remaining pair of groups:
           mì           #  Treat each group of digits as an integer
              ×         #  Multiply those integers
                d       # Return true if at least one of the results...
                 ¥Uì    # ... Is equal to the original number

```
> 2 votes

---
Tags: code-golf, decision-problem, number-theory, set-partitions
---