问:
Universal Spooky Meme Translator

Introduction

Turns out, aliens love memes just as much as we do. Every alien race we've encountered so far has their own version of 2spooky4me (see the following question) and equivalent, though, with some variation. The inhabitants of planet CUTE1f can't handle a lot of spook, so their preferred spook is 1spooky2me, while skeletor7 memers love them some spook, so they tend to use 9spooky11me.

Challenge

Translating memes is hard work, so you've been tasked with writing a universal meme translator to help these guys access the memenet correctly. Your program will accept a meme and a transformation to apply to the digit sequences in that meme to make it appropriate for the inhabitants of a different planet.

Input

Your program will receive two string inputs:

The input meme (e.g. 2spooky4me). Matches [a-zA-Z0-9]+.

The transformation to apply to it (e.g. +1, to go from 2spooky4me to 3spooky5me). Matches [+\-*/^]\d+ (you must accept +, -, *, /, and ^ as operators, regardless of the native representation in your language).

Output

Your program must return a string output (printed to standard output or equivalent) with the given transformation applied to the digit sequences in the input meme. In a weird turn of events, it also turns out that all races encountered so far prefer integral memes over fractional ones, so these transformations should perform integer arithmetic (e.g. 1spooky1me /2 should result in 0spooky0me).

Examples

Standard arithmetic operations apply:

```<code>Input:  2spooky4me +1
Output: 3spooky5me

Input:  2spooky4me -1
Output: 1spooky3me

Input:  2spooky4me *15
Output: 30spooky60me

Input:  10spooky900me /5
Output: 2spooky180me
</code>```

Digit sequences are integral; integer truncation should occur in cases like this:

```<code>Input:  idontunderstandmemes3 /2
Output: idontunderstandmemes1
</code>```

Your input may not have any digit sequences:

```<code>Input:  notreallyafunnymeme *100
Output: notreallyafunnymeme
</code>```

You must support exponentiation, even if it is not a native operation in your language of choice:

```<code>Input:  2spooky4me ^3
Output: 8spooky64me
</code>```

There's no limit on string length of number of digit sequences in the string:

```<code>Input:  some1meme2sequences3can4be5really6long7 /2
Output: some0meme1sequences1can2be2really3long3
</code>```

Addendum

If your language supports arbitrary-precision integers as a language feature, you must use those. If it does not, you do not need to support arbitrary-precision integers. For example, you must use Integer in Haskell instead of Int because it's available as part of the language; in Java, you are not required to use BigInteger because it's a library feature, not a language feature.

```<code>Input:  2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000spooky4me /2
Output: 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000spooky2me
</code>```

This is code-golf, so standard loopholes are forbidden, and the shortest answer in bytes wins!

Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code>## Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code>## Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code>## Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the snippet:

```<code>## [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
Ruby, <s>50</s> <s>44</s> 43 bytes

FGITW answer. Gotta go fast!

Thanks to @Neil for saving 6 bytes.

Oh right, crossed out 44 is still 44

```<code>->m,t{m.gsub(/\d+/){eval$&+t.sub(?^,'**')}}
</code>```

Title: Universal Spooky Meme Translator

Body:
Ruby, <s>50</s> <s>44</s> 43 bytes

FGITW answer. Gotta go fast!

Thanks to @Neil for saving 6 bytes.

Oh right, crossed out 44 is still 44

->m,t{m.gsub(/\d+/){eval$&+t.sub(?^,'**')}}


答:
JavaScript (ES7), <s>58</s> 57 bytes

```<code>(s,t)=>s.replace(/\d+/g,n=>0|eval(n+t.replace('^','**')))
</code>```

Edit: Saved 1 byte when I remembered that replace also works on literal strings.

ContentLicense: CC BY-SA 3.0

Title: Universal Spooky Meme Translator

Body:
Introduction

Turns out, aliens love memes just as much as we do. Every alien race we've encountered so far has their own version of 2spooky4me (see the following question) and equivalent, though, with some variation. The inhabitants of planet CUTE1f can't handle a lot of spook, so their preferred spook is 1spooky2me, while skeletor7 memers love them some spook, so they tend to use 9spooky11me.

Challenge

Translating memes is hard work, so you've been tasked with writing a universal meme translator to help these guys access the memenet correctly. Your program will accept a meme and a transformation to apply to the digit sequences in that meme to make it appropriate for the inhabitants of a different planet.

Input

Your program will receive two string inputs:

The input meme (e.g. 2spooky4me). Matches [a-zA-Z0-9]+.

The transformation to apply to it (e.g. +1, to go from 2spooky4me to 3spooky5me). Matches [+\-*/^]\d+ (you must accept +, -, *, /, and ^ as operators, regardless of the native representation in your language).

Output

Your program must return a string output (printed to standard output or equivalent) with the given transformation applied to the digit sequences in the input meme. In a weird turn of events, it also turns out that all races encountered so far prefer integral memes over fractional ones, so these transformations should perform integer arithmetic (e.g. 1spooky1me /2 should result in 0spooky0me).

Examples

Standard arithmetic operations apply:

```<code>Input:  2spooky4me +1
Output: 3spooky5me

Input:  2spooky4me -1
Output: 1spooky3me

Input:  2spooky4me *15
Output: 30spooky60me

Input:  10spooky900me /5
Output: 2spooky180me
</code>```

Digit sequences are integral; integer truncation should occur in cases like this:

```<code>Input:  idontunderstandmemes3 /2
Output: idontunderstandmemes1
</code>```

Your input may not have any digit sequences:

```<code>Input:  notreallyafunnymeme *100
Output: notreallyafunnymeme
</code>```

You must support exponentiation, even if it is not a native operation in your language of choice:

```<code>Input:  2spooky4me ^3
Output: 8spooky64me
</code>```

There's no limit on string length of number of digit sequences in the string:

```<code>Input:  some1meme2sequences3can4be5really6long7 /2
Output: some0meme1sequences1can2be2really3long3
</code>```

Addendum

If your language supports arbitrary-precision integers as a language feature, you must use those. If it does not, you do not need to support arbitrary-precision integers. For example, you must use Integer in Haskell instead of Int because it's available as part of the language; in Java, you are not required to use BigInteger because it's a library feature, not a language feature.

```<code>Input:  2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000spooky4me /2
Output: 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000spooky2me
</code>```

This is code-golf, so standard loopholes are forbidden, and the shortest answer in bytes wins!

Leaderboard

The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code>## Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code>## Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code>## Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the snippet:

```<code>## [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

Body:
JavaScript (ES7), <s>58</s> 57 bytes

(s,t)=>s.replace(/\d+/g,n=>0|eval(n+t.replace('^','**')))

Edit: Saved 1 byte when I remembered that replace also works on literal strings.


答:
Python 2, <s>156</s> <s>89</s> <s>88</s> 87 bytes

Inspired by the other answers that use their languages' substitution function with a function handler to process the numeric parts of the long input string with the operator. Unlucky for Python, the ^ must be replaced by **, which costs a whopping 18 bytes. The .group(0) call just to access the match object's string representation does not make things better...

Thanks to QPaysTaxes for spotting a spurious space and RootTwo for the unnecessary argument to .group!

```<code>import re
lambda i,o:re.sub(r'\d+',lambda p:str(eval(p.group()+o.replace('^','**'))),i)
</code>```

Title: Universal Spooky Meme Translator

Body:
Python 2, <s>156</s> <s>89</s> <s>88</s> 87 bytes

Inspired by the other answers that use their languages' substitution function with a function handler to process the numeric parts of the long input string with the operator. Unlucky for Python, the ^ must be replaced by **, which costs a whopping 18 bytes. The .group(0) call just to access the match object's string representation does not make things better...

Thanks to QPaysTaxes for spotting a spurious space and RootTwo for the unnecessary argument to .group!

import re
lambda i,o:re.sub(r'\d+',lambda p:str(eval(p.group()+o.replace('^','**'))),i)


答:
Javascript (ES6) 99 bytes

Another example, why we hate to wait for ES7 to get compatibility

```<code>(a,b)=>a.match(/\d+|\D+/g).map(_=>(d=- -_)?eval(b[0]=="\^"?Math.pow(_,b.slice(1)):d+b)|0:_).join``
</code>```

Runnable example:

f=(a,b)=>a.match(/\d+|\D+/g).map(_=>(d=- -_)?Math.ceil(eval(b[0]=="\^"?Math.pow(_,b.slice(1)):d+b)):_).join``

alert(f(prompt("Enter string!"), prompt("Enter operation!")));```

Title: Universal Spooky Meme Translator

Body:
Javascript (ES6) 99 bytes

Another example, why we hate to wait for ES7 to get compatibility

(a,b)=>a.match(/\d+|\D+/g).map(_=>(d=- -_)?eval(b[0]=="\^"?Math.pow(_,b.slice(1)):d+b)|0:_).join``

Runnable example:

f=(a,b)=>a.match(/\d+|\D+/g).map(_=>(d=- -_)?Math.ceil(eval(b[0]=="\^"?Math.pow(_,b.slice(1)):d+b)):_).join``

alert(f(prompt("Enter string!"), prompt("Enter operation!")));


问:
Columnar Transposition Cipher

Columnar Transposition Cipher

While I have plenty of programs I have written for more advanced ciphers, I just realised I don't actually have one for one of the simplest: Columnar Transposition. The cipher, in case you don't know, works as follows:

First, you take the key, and write it as numbers. The numbers are made by replacing the letter which comes first in the alphabet with 1, the letter that comes next 2 and so on, ignoring duplicates (the key GOAT would become 2314). These numbers are the headers of the columns.

```<code>2314
----
</code>```

Next, you write your message under the columns.

```<code>2314
----
Hell
o Wo
rld!
</code>```

Finally, rearrange the columns into the numerical order in which they would fall, and read the ciphertext across.

```<code>1234
----
lHel
Wo o
drl!
</code>```

Which will result in your encoded text: lHelWo odrl!

Rules

Each submission should be either a full program or function. If it is a function, it must be runnable by only needing to add the function call to the bottom of the program. Anything else (e.g. headers in C), must be included.

There must be a free interpreter/compiler available for your language.

If it is possible, provide a link to a site where your program can be tested.

Your program must not write anything to STDERR.

Your program should take input as an argument or from STDIN (or the closest alternative in your language).

Standard loopholes are forbidden.

Requirements

Case must be preserved.

Your cipher should be 'irregular', that is, if there are any spaces left after you have written out your message, it is treated as if it were a normal space character.

Only encryption is required, decryption may come in a later challenge.

Input should be taken from STDIN with the key on the first line, and the plaintext on the second. If you are taking input as an argument, please specify how this is done for your language.

The key can be in any case.

Duplicates in the key should be ignored - that is, ABCDB would become ABCD. Duplicates also apply in any case.

Trailing whitespace is included.

Test Cases

```<code>CBABD, Duplicates are ignored. ==> puDlacit sea eriongr.de
bDaEc, Key can be in multicase! ==> yKce  aenbn mi tucliea s!
</code>```

Full example, with 'surplus space' rule.

```<code>ADCB
----
"Goo
d Mo
rnin
g!"
he c
alle
d.

ABCD
----
"ooG
dom
rnin
g "!
hc e
aell
d  .

Message: "ooGdom rning "!hc eaelld  .
</code>```

Scoring

code-golf is how we score this challenge!

Submissions

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code># Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code># Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code># Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the leaderboard snippet:

```<code># [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 79810; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 53406; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '
' + c.body.replace(OVERRIDE_REG, '') + '
';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });

  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/ b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}</code>```

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
JavaScript (ES6), 170 bytes

```<code>(k,s)=>[...s].map((c,i)=>(i%l||(r+=t.join``,t=[]),t[[...k].sort().search(k[i%l])]=c),k=[...k=k.toLowerCase()].filter((c,i)=>i==k.search(c)),l=k.length,r=t=[])&&r+t.join``
</code>```

Preprocessing the key is a waste of 56 bytes...

Title: Columnar Transposition Cipher

Body:
JavaScript (ES6), 170 bytes

(k,s)=>[...s].map((c,i)=>(i%l||(r+=t.join``,t=[]),t[[...k].sort().search(k[i%l])]=c),k=[...k=k.toLowerCase()].filter((c,i)=>i==k.search(c)),l=k.length,r=t=[])&&r+t.join``

Preprocessing the key is a waste of 56 bytes...


答:
PowerShell v2+, <s>139</s> 137 bytes

```<code>param($a,$b)-join($a-split"(\d+)"|%{if($_-match"\d+"){if($b[0]-ne'^'){[math]::Floor((iex $_$b))}else{"$_*"*$b.Trim('^')+1|iex}}else{$_}})
</code>```

Ooof ... 47 bytes just to account for ^ since that's not a native operator in PowerShell. Saved 2 bytes thanks to @TessellatingHeckler.

Takes input as $a=<word>, $b=<operation>, like .\universal-spooky-meme.ps1 2spooky4me ^3. We -split $a on digits, enclosing that in parens so we keep the delimiters, and pipe the resultant array through a loop |%{...}. If the current piece is a number, we're in the first if. We need to check whether the first character of $b is ^. If it's not, we simply concatenate our current piece and $b and send it to iex (similar to eval), then leave that on the pipeline. Otherwise, we need to create an exponentiation string with "$_*"*$b.Trim('^')+1 and pipe that to iex, and leave that on the pipeline. For the given 2spooky4me ^3 example, this will be 2*2*2*1 and 4*4*4*1, respectively.

Otherwise, we just leave the string as-is on the pipeline.

All of those results are gathered from the pipeline with the encapsulating parens before being -joined back together into one string. That is the re-left on the pipeline, and output is implicit at program termination.

Examples

```<code>PS C:\Tools\Scripts\golfing> .\universal-spooky-meme.ps1 2spooky4me ^5
32spooky1024me

PS C:\Tools\Scripts\golfing> .\universal-spooky-meme.ps1 2spooky4me /3
0spooky1me
</code>```

Title: Universal Spooky Meme Translator

Body:
PowerShell v2+, <s>139</s> 137 bytes

param($a,$b)-join($a-split"(\d+)"|%{if($_-match"\d+"){if($b[0]-ne'^'){[math]::Floor((iex $_$b))}else{"$_*"*$b.Trim('^')+1|iex}}else{$_}})

Ooof ... 47 bytes just to account for ^ since that's not a native operator in PowerShell. Saved 2 bytes thanks to @TessellatingHeckler.

Takes input as $a=<word>, $b=<operation>, like .\universal-spooky-meme.ps1 2spooky4me ^3. We -split $a on digits, enclosing that in parens so we keep the delimiters, and pipe the resultant array through a loop |%{...}. If the current piece is a number, we're in the first if. We need to check whether the first character of $b is ^. If it's not, we simply concatenate our current piece and $b and send it to iex (similar to eval), then leave that on the pipeline. Otherwise, we need to create an exponentiation string with "$_*"*$b.Trim('^')+1 and pipe that to iex, and leave that on the pipeline. For the given 2spooky4me ^3 example, this will be 2*2*2*1 and 4*4*4*1, respectively.

Otherwise, we just leave the string as-is on the pipeline.

All of those results are gathered from the pipeline with the encapsulating parens before being -joined back together into one string. That is the re-left on the pipeline, and output is implicit at program termination.

Examples

PS C:\Tools\Scripts\golfing> .\universal-spooky-meme.ps1 2spooky4me ^5
32spooky1024me

PS C:\Tools\Scripts\golfing> .\universal-spooky-meme.ps1 2spooky4me /3
0spooky1me


问:
Zeroes at the end of a factorial
Write a program or function that finds the number of zeroes at the end of n! in base 10, where n is an input number (in any desired format).

It can be assumed that n is a positive integer, meaning that n! is also an integer. There are no zeroes after a decimal point in n!. Also, it can be assumed that your programming language can handle the value of n and n!.

Test cases

```<code>1
==> 0

5
==> 1

100
==> 24

666
==> 165

2016
==> 502

1234567891011121314151617181920
==> 308641972752780328537904295461
</code>```

This is code golf. Standard rules apply. The shortest code in bytes wins.

答:
Haskell, 39 bytes

Can't compete with @xnor, but it was fun and the result is a different approach:

```<code>f n=sum$[1..n]>>= \i->1<$[5^i,2*5^i..n]
</code>```

Title: Zeroes at the end of a factorial

Body:
Haskell, 39 bytes

Can't compete with @xnor, but it was fun and the result is a different approach:

f n=sum$[1..n]>>= \i->1<$[5^i,2*5^i..n]


答:
Julia, <s>71</s> <s>59</s> 54 bytes

/ =÷
x%y=replace(x,r"\d+",t->"big($t)"y|>parse|>eval)
```

The requirement to use big if available makes this a lot longer than it could be...

Try it online!

Title: Universal Spooky Meme Translator

Body:
Julia, <s>71</s> <s>59</s> 54 bytes

/ =÷
x%y=replace(x,r"\d+",t->"big($t)"y|>parse|>eval)

The requirement to use big if available makes this a lot longer than it could be...

<a href="http://julia.tryitonline.net/#code=LyA9w7cKeCV5PXJlcGxhY2UoeCxyIlxkKyIsdC0-ImJpZygkdCkieXw-cGFyc2V8PmV2YWwpCiAKcHJpbnRsbigiMnNwb29reTRtZSIlIisxIikKcHJpbnRsbigiMnNwb29reTRtZSIlIi0xIikKcHJpbnRsbigiMnNwb29reTRtZSIlIioxNSIpCnByaW50bG4oIjEwc3Bvb2t5OTAwbWUiJSIvNSIpCnByaW50bG4oImlkb250dW5kZXJzdGFuZG1lbWVzMyIlIi8yIikKcHJpbnRsbigibm90cmVhbGx5YWZ1bm55bWVtZSIlIioxMDAiKQpwcmludGxuKCIyc3Bvb2t5NG1lIiUiXjMiKQpwcmludGxuKCJzb21lMW1lbWUyc2VxdWVuY2VzM2NhbjRiZTVyZWFsbHk2bG9uZzciJSIvMiIpCnByaW50bG4oIjIwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDBzcG9va3k0bWUiJSIvMiIpCnByaW50bG4oIjJiaWc0aW50IiUiKjkyMjMzNzIwMzY4NTQ3NzU4MDciKQ&input=" rel="nofollow">Try it online!


答:
Python 3.5, 139

```<code>def f(a,b):a,s,j=a.lower(),sorted,''.join;a=s({*a},key=a.find);l=len(a);return j(map(j,[*zip(*s(zip(*zip(*[iter(a+[*b+' '*l])]*l))))][1:]))
</code>```

Slightly more readable version:

```<code>def f(a, b):
    a = a.lower()
    # Remove duplicates
    a = sorted({*a}, key=a.find)
    l = len(a)
    # Add the key
    z = zip(*[iter(a + [*b, *[''] * l])]*l)
    # Sort tuples lexicographically, remove the key
    z = [*zip(*sorted(zip(*z)))][1:]
    return ''.join(map(''.join, z))
</code>```

Title: Columnar Transposition Cipher

Body:
Columnar Transposition Cipher

While I have plenty of programs I have written for more advanced ciphers, I just realised I don't actually have one for one of the simplest: Columnar Transposition. The cipher, in case you don't know, works as follows:

First, you take the key, and write it as numbers. The numbers are made by replacing the letter which comes first in the alphabet with 1, the letter that comes next 2 and so on, ignoring duplicates (the key GOAT would become 2314). These numbers are the headers of the columns.

```<code>2314
----
</code>```

Next, you write your message under the columns.

```<code>2314
----
Hell
o Wo
rld!
</code>```

Finally, rearrange the columns into the numerical order in which they would fall, and read the ciphertext across.

```<code>1234
----
lHel
Wo o
drl!
</code>```

Which will result in your encoded text: lHelWo odrl!

Rules

Each submission should be either a full program or function. If it is a function, it must be runnable by only needing to add the function call to the bottom of the program. Anything else (e.g. headers in C), must be included.

There must be a free interpreter/compiler available for your language.

If it is possible, provide a link to a site where your program can be tested.

Your program must not write anything to STDERR.

Your program should take input as an argument or from STDIN (or the closest alternative in your language).

Standard loopholes are forbidden.

Requirements

Case must be preserved.

Your cipher should be 'irregular', that is, if there are any spaces left after you have written out your message, it is treated as if it were a normal space character.

Only encryption is required, decryption may come in a later challenge.

Input should be taken from STDIN with the key on the first line, and the plaintext on the second. If you are taking input as an argument, please specify how this is done for your language.

The key can be in any case.

Duplicates in the key should be ignored - that is, ABCDB would become ABCD. Duplicates also apply in any case.

Trailing whitespace is included.

Test Cases

```<code>CBABD, Duplicates are ignored. ==> puDlacit sea eriongr.de
bDaEc, Key can be in multicase! ==> yKce  aenbn mi tucliea s!
</code>```

Full example, with 'surplus space' rule.

```<code>ADCB
----
"Goo
d Mo
rnin
g!"
he c
alle
d.

ABCD
----
"ooG
dom
rnin
g "!
hc e
aell
d  .

Message: "ooGdom rning "!hc eaelld  .
</code>```

Scoring

code-golf is how we score this challenge!

Submissions

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code># Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code># Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code># Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the leaderboard snippet:

```<code># [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 79810; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 53406; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '
' + c.body.replace(OVERRIDE_REG, '') + '
';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });

  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/ b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}</code>```

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

Body:
Python 3.5, 139

def f(a,b):a,s,j=a.lower(),sorted,''.join;a=s({*a},key=a.find);l=len(a);return j(map(j,[*zip(*s(zip(*zip(*[iter(a+[*b+' '*l])]*l))))][1:]))

Slightly more readable version:

def f(a, b):
    a = a.lower()
    # Remove duplicates
    a = sorted({*a}, key=a.find)
    l = len(a)
    # Add the key
    z = zip(*[iter(a + [*b, *[''] * l])]*l)
    # Sort tuples lexicographically, remove the key
    z = [*zip(*sorted(zip(*z)))][1:]
    return ''.join(map(''.join, z))


答:
Perl 6, 23 bytes

{[+] -$_,$_,*div 5…0}
{sum -$_,$_,*div 5...0}
```

<p>I could get it shorter if <code>^...</code> was added to Perl 6 <code>{sum $_,*div 5^...0}</code>.<br>
It should be more memory efficient for larger numbers if you added a <code>lazy</code> modifier between <code>sum</code> and the sequence generator.</p>

<h3>Explanation:</h3>

<pre class="lang-perl6 prettyprint-override"><code>{ # implicitly uses $_ as its parameter
  sum

    # produce a sequence
    -$_,     # negate the next value
     $_,     # start of the sequence

     * div 5 # Whatever lambda that floor divides its input by 5

             # the input being the previous value in the sequence,
             # and the result gets appended to the sequence

     ...     # continue to do that until:

     0       # it reaches 0
}
</code>```

Test:

#! /usr/bin/env perl6

use v6.c;
use Test;

my @test = (
     1,   0,
     5,   1,
   100,  24,
   666, 165,
  2016, 502,
  1234567891011121314151617181920,
        308641972752780328537904295461,

  # [*] 5 xx 100
  7888609052210118054117285652827862296732064351090230047702789306640625,
        1972152263052529513529321413206965574183016087772557511925697326660156,
);

plan @test / 2;

# make it a postfix operator, because why not
my &postfix:<!0> = {[+] -$_,$_,*div 5...0}

for @test -> $input, $expected {
  is $input!0, $expected, "$input => $expected"
}

diag "runs in {now - INIT now} seconds"
```

<pre class="lang-none prettyprint-override"><code>1..7
ok 1 - 1 => 0
ok 2 - 5 => 1
ok 3 - 100 => 24
ok 4 - 666 => 165
ok 5 - 2016 => 502
ok 6 - 1234567891011121314151617181920 => 308641972752780328537904295461
ok 7 - 7888609052210118054117285652827862296732064351090230047702789306640625 => 1972152263052529513529321413206965574183016087772557511925697326660156
# runs in 0.0252692 seconds
</code>```

( That last line is slightly misleading, as MoarVM has to start, load the Perl 6 compiler and runtime, compile the code, and run it. So it actually takes about a second and a half in total.

That is still significantly faster than it was to check the result of the last test with WolframAlpha.com )

Title: Zeroes at the end of a factorial

Body:
Write a program or function that finds the number of zeroes at the end of n! in base 10, where n is an input number (in any desired format).

It can be assumed that n is a positive integer, meaning that n! is also an integer. There are no zeroes after a decimal point in n!. Also, it can be assumed that your programming language can handle the value of n and n!.

Test cases

```<code>1
==> 0

5
==> 1

100
==> 24

666
==> 165

2016
==> 502

1234567891011121314151617181920
==> 308641972752780328537904295461
</code>```

This is code golf. Standard rules apply. The shortest code in bytes wins.

Body:
Perl 6, 23 bytes

{[+] -$_,$_,*div 5…0}
{sum -$_,$_,*div 5...0}

I could get it shorter if ^... was added to Perl 6 {sum $_,*div 5^...0}.

It should be more memory efficient for larger numbers if you added a lazy modifier between sum and the sequence generator.

Explanation:

{ # implicitly uses $_ as its parameter
  sum

    # produce a sequence
    -$_,     # negate the next value
     $_,     # start of the sequence

     * div 5 # Whatever lambda that floor divides its input by 5

             # the input being the previous value in the sequence,
             # and the result gets appended to the sequence

     ...     # continue to do that until:

     0       # it reaches 0
}

Test:

#! /usr/bin/env perl6

use v6.c;
use Test;

my @test = (
     1,   0,
     5,   1,
   100,  24,
   666, 165,
  2016, 502,
  1234567891011121314151617181920,
        308641972752780328537904295461,

  # [*] 5 xx 100
  7888609052210118054117285652827862296732064351090230047702789306640625,
        1972152263052529513529321413206965574183016087772557511925697326660156,
);

plan @test / 2;

# make it a postfix operator, because why not
my &postfix:<!0> = {[+] -$_,$_,*div 5...0}

for @test -> $input, $expected {
  is $input!0, $expected, "$input => $expected"
}

diag "runs in {now - INIT now} seconds"

1..7
ok 1 - 1 => 0
ok 2 - 5 => 1
ok 3 - 100 => 24
ok 4 - 666 => 165
ok 5 - 2016 => 502
ok 6 - 1234567891011121314151617181920 => 308641972752780328537904295461
ok 7 - 7888609052210118054117285652827862296732064351090230047702789306640625 => 1972152263052529513529321413206965574183016087772557511925697326660156
# runs in 0.0252692 seconds

( That last line is slightly misleading, as MoarVM has to start, load the Perl 6 compiler and runtime, compile the code, and run it. So it actually takes about a second and a half in total.

That is still significantly faster than it was to check the result of the last test with WolframAlpha.com )


答:
Javascript, 155 <s>159</s> <s>149</s> <s>151</s>

```<code>(w,s)=>(a='',z=new Set,w=[...[...w].map(z.add,z)[0]].sort(),eval(`s.match(/.{1,${z.size}}/g)`).map(l=>[...l].map((c,i)=>a+=l[[...z].indexOf(w[i])]||'')),a)
</code>```

Saved 4 bytes thanks @Bergi.

Here it goes, ungolfed and explained:

function ColumnarTranspositionCipher(word, sentence) {
    var answer = "";

    // the own methods of Set does it shorter than a raw Object
    var z = new Set;

    // As Set only allows unique keys, we get the processed key by adding
    [...word].forEach(function(letter) {
        z.add(letter);
    });

    // word now has the sorted key
    word = [...z].sort(),

    // divide sentence by the processed key's length
    sentence = sentence.match(RegExp(".{1," + z.size + "}", "g"));

    sentence.forEach(function(row) {
        [...row].forEach(function(letter, newIndex) {

            // get the old index - relative to the previous sorted/unsorted keys
            var oldIndex = [...z].indexOf(word[newIndex]);

            // and add to the answer
            answer += row[oldIndex] || "";
        });
    });

    return answer;
}

r= code=> output.innerHTML += '\n>  ' + code + '\n<- "' + eval(code) + '"\n';
r("ColumnarTranspositionCipher('GOAT', 'Hello World!')");
r("ColumnarTranspositionCipher('CBABD', 'Duplicates are ignored.')");
r("ColumnarTranspositionCipher('aBeCd', 'Key can be in multicase!')");```
<pre class="snippet-code-html lang-html prettyprint-override"><code><pre id=output>``````

Title: Columnar Transposition Cipher

Body:
Javascript, 155 <s>159</s> <s>149</s> <s>151</s>

(w,s)=>(a='',z=new Set,w=[...[...w].map(z.add,z)[0]].sort(),eval(`s.match(/.{1,${z.size}}/g)`).map(l=>[...l].map((c,i)=>a+=l[[...z].indexOf(w[i])]||'')),a)

Saved 4 bytes thanks @Bergi.

Here it goes, ungolfed and explained:

function ColumnarTranspositionCipher(word, sentence) {
    var answer = "";

    // the own methods of Set does it shorter than a raw Object
    var z = new Set;

    // As Set only allows unique keys, we get the processed key by adding
    [...word].forEach(function(letter) {
        z.add(letter);
    });

    // word now has the sorted key
    word = [...z].sort(),

    // divide sentence by the processed key's length
    sentence = sentence.match(RegExp(".{1," + z.size + "}", "g"));

    sentence.forEach(function(row) {
        [...row].forEach(function(letter, newIndex) {

            // get the old index - relative to the previous sorted/unsorted keys
            var oldIndex = [...z].indexOf(word[newIndex]);

            // and add to the answer
            answer += row[oldIndex] || "";
        });
    });

    return answer;
}

r= code=> output.innerHTML += '\n>  ' + code + '\n<- "' + eval(code) + '"\n';
r("ColumnarTranspositionCipher('GOAT', 'Hello World!')");
r("ColumnarTranspositionCipher('CBABD', 'Duplicates are ignored.')");
r("ColumnarTranspositionCipher('aBeCd', 'Key can be in multicase!')");

<pre id=output></pre>


答:
Haskell, <s>98</s> <s>84</s> 83 bytes

```<code>import Data.List
h c=map snd.sort.zip((<$>nub((`mod`32).fromEnum<$>c)).(,)=<<[1..])
</code>```

Usage example: h "CBAbD" "Duplicates are ignored." -> "puDlacit sea eriongr.de".

How it works:

```<code>       nub((`mod`32).fromEnum<$>c)  -- turn key to lowercase and remove duplicates
    (<$>      ).(,)=<<[1..]         -- make pairs of (number , char from key)
                                    -- for every character in the key and every
                                    -- number starting with 1. This builds and
                                    -- infinite list, e.g. for the key "cba":
                                    -- (1,c),(1,b),(1,a),(2,c),(2,b),(2,a),(3,c)...
              zip(          )       -- zip this list with input String, e.g. for
                                    -- the string "mnopq" with the key from above:
                                    -- ((1,c),m),((1,b),n),((1,a),o),((2,c),p),((2,b),q)
                                    -- zip stops at the end of the shorter list
         sort                       -- sort lexicographically
 map snd                            -- extract characters of the string
</code>```

Title: Columnar Transposition Cipher

Body:
Haskell, <s>98</s> <s>84</s> 83 bytes

import Data.List
h c=map snd.sort.zip((<$>nub((`mod`32).fromEnum<$>c)).(,)=<<[1..])

Usage example: h "CBAbD" "Duplicates are ignored." -> "puDlacit sea eriongr.de".

How it works:

       nub((`mod`32).fromEnum<$>c)  -- turn key to lowercase and remove duplicates
    (<$>      ).(,)=<<[1..]         -- make pairs of (number , char from key)
                                    -- for every character in the key and every
                                    -- number starting with 1. This builds and
                                    -- infinite list, e.g. for the key "cba":
                                    -- (1,c),(1,b),(1,a),(2,c),(2,b),(2,a),(3,c)...
              zip(          )       -- zip this list with input String, e.g. for
                                    -- the string "mnopq" with the key from above:
                                    -- ((1,c),m),((1,b),n),((1,a),o),((2,c),p),((2,b),q)
                                    -- zip stops at the end of the shorter list
         sort                       -- sort lexicographically
 map snd                            -- extract characters of the string


答:
Perl, <s>36</s> 34 bytes

```<code>s/\d+/"0|$&$^I"=~s#\^#**#r/gee
</code>```

The source code is 30 bytes long and it requires the switches -pi (+4 bytes). It takes the first input from STDIN, the second input as an argument to -i.

Thanks to @DenisIbaev for golfing off 2 bytes!

Test it on Ideone.

Title: Universal Spooky Meme Translator

Body:
Perl, <s>36</s> 34 bytes

s/\d+/"0|$&$^I"=~s#\^#**#r/gee

The source code is 30 bytes long and it requires the switches -pi (+4 bytes). It takes the first input from STDIN, the second input as an argument to -i.

Thanks to @DenisIbaev for golfing off 2 bytes!

Test it on Ideone.


答:
Lua, <s>145</s> 93 bytes

```<code>r=io.read;m=r()o=r()m=m:gsub("%d",function(n)return loadstring("return..."..o)(n)end)print(m)
</code>```

Title: Universal Spooky Meme Translator

Body:
Lua, <s>145</s> 93 bytes

r=io.read;m=r()o=r()m=m:gsub("%d",function(n)return loadstring("return..."..o)(n)end)print(m)


问:
Counting Quipu: Base 10 in the New World
Quipus are an ancient device used by the Inca in the Precolumbian era to record numbers in a base ten positional system of knots on a cord, which works as follows:

Each cluster of knots is a digit, and there are three main types of knots: simple overhand knots; "long knots", consisting of an overhand knot with one or more additional turns; and figure-eight knots.

Powers of ten are shown by position along the string, and this position is aligned between successive strands.

Digits in positions for 10 and higher powers are represented by clusters of simple knots (e.g., 40 is four simple knots in a row in the "tens" position).

Digits in the "ones" position are represented by long knots (e.g., 4 is a knot with four turns). Because of the way the knots are tied, the digit 1 cannot be shown this way and is represented in this position by a figure-of-eight knot.

Zero is represented by the absence of a knot in the appropriate position.

Details

For this challenge, each strand of a quipu represents a single number (though, as the Wikipedia article states, you can represent many numbers on one strand, in this challenge, we shall not).

Knots

Each knot will be represented by a single ASCII character.

. represents a simple knot

: represents a one turn of a long knot

8 represents a figure-eight knot

| represents the absence of a knot as well as a delimiter between the digits.

Constructing Quipus

Quipu are constructed following these rules.

Strands run top to bottom in descending order of position (as in, the units digit will be at the bottom end of a strand). Digits along a strand are separated by the character (|).

The power of 10 a digit represents is determined by its position along the strand in the same way a digit's power of 10 would be calculated using its index in a number with our number system. That is, 24 with a 2 in the tens place and a 4 in the units place, will be represented by two knots, a delimiter (|), then four knots.

Digits in the same position are aligned towards the bottom of the strand. If one digit in a position will have less knots than other digits of other numbers in the same position, the absence of those knots is represented by (|).

Consecutive simple knots (.) represent a value in their position.

Every digit is represented by at least 1 character. When a digits value is 0 for all numbers in a quipu, it is represented by the absence of a knot (|).

The units place is treated specially. A one in the units place is represented by a figure-eight knot (8). A value of two or more in the units place is represented by consecutive long knots (:).

When the units digit is 0 for all numbers in a quipu the absence of a knot is not printed but, the trailing delimiter for the tens digit is preserved.

There is no delimiter following the units digit.

Rules

Input will consist of a non-empty list of non-negative integers that may be received through any of the default input methods. You may assume that these integers are all less than or equal to 2147483647 or 2^31-1. While the test cases are space-delimited, your input format can separate inputs in any way that is convenient for your language, whether that be comma-separated, newline-separated, in an array, and so on.

Output consists of a single Quipu constructed according to the rules described above. Output may be given through any of the default output methods.

Your code should be a program or a function, though it does not need to be a named function.

Knots take some time to tie so to save time, your code as short as possible.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

Examples

Input:

```<code>5 3 1 0
</code>```

Output:

```<code>:|||
:|||
::||
::||
::8|
</code>```

Input:

```<code>50 30 10 0
</code>```

Output:

```<code>.|||
.|||
..||
..||
...|
||||
</code>```

Input:

```<code>330
</code>```

Output:

```<code>.
.
.
|
.
.
.
|
</code>```

Input:

```<code>204 1
</code>```

Output:

```<code>.|
.|
||
||
||
:|
:|
:|
:8
</code>```

Input:

```<code>201 0 100 222
</code>```

Output:

```<code>.||.
.|..
||||
|||.
|||.
||||
|||:
8||:
</code>```

Input:

```<code>:|||
:|||
::||
::||
::8|
</code>```0

Output:

```<code>:|||
:|||
::||
::||
::8|
</code>```1

Input:

```<code>:|||
:|||
::||
::||
::8|
</code>```2

Output:

```<code>|
</code>```

Longer test cases

Further Reading

Ancientscripts: Quipu

The Quipu, Pre-Inca Data Structure

答:
R - 446 444

I see there is no R solution yet, so here is one. The function takes a vector with integers.

```<code>function(x){r=nchar(max(x));c=length(x);m=matrix(0,r,c);for(i in 1:c){t=as.numeric(strsplit(as.character(x[i]),"")[[1]]);m[(r+1-length(t)):r,i]=t};Q=c();for(i in 1:r){d=m[i,];z=ifelse(max(d)>0,max(d),1);q=matrix("|",z,c);for(j in 1:c){v=m[i,j];if(i==r){if(v==1)q[z,j]=8;if(v>1)q[(z-v+1):z,j]=rep(":",v)};if(i<r){if(v>0)q[(z-v+1):z,j]=rep(".",v)}};if(i!=1&sum(d)>0)q=rbind(rep("|",c),q);Q=rbind(Q,q)};for(i in 1:nrow(Q))cat(Q[i,],sep="",fill=T)}
</code>```

Ungolfed

```<code># Some test data
test <- c(201, 0, 100, 222, 53)

# Define function
quipu <- function (x) {

    # Create matrix with a row for each digit and a column for each number
    r=nchar(max(x));c=length(x);m <- matrix(0,r,c)
    for(i in 1:c) {
        t=as.numeric(strsplit(as.character(x[i]),"")[[1]])
        m[(r+1-length(t)):r,i]=t
    }

    # Loop through each row (digit) starting at the top of the quipu
    Q=c() # Empty matrix to store quipu
    for(i in 1:r){

        d=m[i,]
        z=ifelse(max(d)>0,max(d),1)
        q=matrix("|",z,c)

        # Loop through each column (number in the vector) starting at the leftmost quipu
        for(j in 1:c){

            # The digit
            v=m[i,j]

            # If it is the last segment of the quipu
            if(i==r){
                if(v==1){q[z,j]=8} # If unit digit =1
                if(v>1){q[(z-v+1):z,j]=rep(":",v)} # If unit digit >1
            }

            # If it is not the last segment of the quipu
            if(i<r){
                if(v>0){q[(z-v+1):z,j]=rep(".",v)} # If non-unit digit >0
            }
        }

        # Add segment to Q
        if(i!=1 & sum(d)>0){q=rbind(rep("|",c),q)}
        Q=rbind(Q,q)
    }

    # Print quipu
    for(i in 1:nrow(Q)) {cat(Q[i,], sep="", fill=T)}
}

# Test
quipu(test)
</code>```

Body:
R - 446 444

I see there is no R solution yet, so here is one. The function takes a vector with integers.

function(x){r=nchar(max(x));c=length(x);m=matrix(0,r,c);for(i in 1:c){t=as.numeric(strsplit(as.character(x[i]),"")[[1]]);m[(r+1-length(t)):r,i]=t};Q=c();for(i in 1:r){d=m[i,];z=ifelse(max(d)>0,max(d),1);q=matrix("|",z,c);for(j in 1:c){v=m[i,j];if(i==r){if(v==1)q[z,j]=8;if(v>1)q[(z-v+1):z,j]=rep(":",v)};if(i<r){if(v>0)q[(z-v+1):z,j]=rep(".",v)}};if(i!=1&sum(d)>0)q=rbind(rep("|",c),q);Q=rbind(Q,q)};for(i in 1:nrow(Q))cat(Q[i,],sep="",fill=T)}

Ungolfed

# Some test data
test <- c(201, 0, 100, 222, 53)

# Define function
quipu <- function (x) {

    # Create matrix with a row for each digit and a column for each number
    r=nchar(max(x));c=length(x);m <- matrix(0,r,c)
    for(i in 1:c) {
        t=as.numeric(strsplit(as.character(x[i]),"")[[1]])
        m[(r+1-length(t)):r,i]=t
    }

    # Loop through each row (digit) starting at the top of the quipu
    Q=c() # Empty matrix to store quipu
    for(i in 1:r){

        d=m[i,]
        z=ifelse(max(d)>0,max(d),1)
        q=matrix("|",z,c)

        # Loop through each column (number in the vector) starting at the leftmost quipu
        for(j in 1:c){

            # The digit
            v=m[i,j]

            # If it is the last segment of the quipu
            if(i==r){
                if(v==1){q[z,j]=8} # If unit digit =1
                if(v>1){q[(z-v+1):z,j]=rep(":",v)} # If unit digit >1
            }

            # If it is not the last segment of the quipu
            if(i<r){
                if(v>0){q[(z-v+1):z,j]=rep(".",v)} # If non-unit digit >0
            }
        }

        # Add segment to Q
        if(i!=1 & sum(d)>0){q=rbind(rep("|",c),q)}
        Q=rbind(Q,q)
    }

    # Print quipu
    for(i in 1:nrow(Q)) {cat(Q[i,], sep="", fill=T)}
}

# Test
quipu(test)


答:
RETURN, 17 bytes

```<code>[$[5÷\%$F+][]?]=F
</code>```

Try it here.

Recursive operator lambda. Usage:

```<code>[$[5÷\%$F+][]?]=F666F
</code>```

Explanation

```<code>[             ]=F  Lambda -> Operator F
 $                 Check if top of stack is truthy
  [       ][]?     Conditional
   5÷\%$F+         If so, do x/5+F(x/5)
</code>```

Title: Zeroes at the end of a factorial

Body:
RETURN, 17 bytes

[$[5÷\%$F+][]?]=F

Try it here.

Recursive operator lambda. Usage:

[$[5÷\%$F+][]?]=F666F

Explanation

[             ]=F  Lambda -> Operator F
 $                 Check if top of stack is truthy
  [       ][]?     Conditional
   5÷\%$F+         If so, do x/5+F(x/5)


问:
Inverse regex of compound interest
Koronkorko is the Finnish word for compound interest. We don't want compound interest in our strings, so let's find the shortest possible regular expression to exclude it.

Given a string consisting only of the uppercase alphabetic characters A-Z, determine the shortest possible regular expression that matches the string if it does not contain the substring KORONKORKO. Any string that contains KORONKORKO as a substring should not be matched by the regex.

Only the characters A-Z, [, ], -, ^, , ?, *, +, |, (, and ) should be used in the expression.

I think this can be done with 118 characters in the expression. Can you make it shorter?

Note: This challenge is from Ohjelmointiputka (in Finnish).

答:
204 characters

```<code>(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?[^KO]|[^KR])|[^KO])|[^K])|[^KN])|[^KO])|[^KR])|[^KO])|[^K])*(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?)?)?)?)?)?)?)?)?
</code>```

Generated by turning .*KORONKORKO.* into a finite state machine, inverting the finite state machine, and turning it back into a regex.

Title: Inverse regex of compound interest

Body:
204 characters

(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?[^KO]|[^KR])|[^KO])|[^K])|[^KN])|[^KO])|[^KR])|[^KO])|[^K])*(K((O(R(O(NKORO)*(NK(O(RK)?)?)?)?)?)?K)*(O(R(O(NKORO)*(N(K(O(RK?)?)?)?)?)?)?)?)?

Generated by turning .*KORONKORKO.* into a finite state machine, inverting the finite state machine, and turning it back into a regex.


答:
R, 182 177

Here is the golfed version:

```<code>function(t,k){k=unique(unlist(strsplit(tolower(k),"")));t=unlist(strsplit(t,""));l=length(t);c=length(k);r=ceiling(l/c);t=c(t,rep("",c*r-l));cat(matrix(t,r,c)[order(rank(k)),])}
</code>```

And ungolfed version, which shows how the function takes the data.

```<code># test data
key = "aBeCd"
test = "ABCDEabcdeABCDEabcdeABC!"

# t is the test phrase, k is the key
cipher=function(t,k){
    k=unique(unlist(strsplit(tolower(key),"")))
    t=unlist(strsplit(test,""))
    l=length(t)
    c=length(k)
    r=ceiling(l/c)
    t=c(t,rep("",c*r-l))
    cat(matrix(t,r,c)[order(rank(k)),])
}

# Show that it works
cipher(test,key)
## A B D E C a b d e c A B D E C a b d e c A B !  C
</code>```

The test cases provided by the OP seem incorrect. I intentionally chose a test case here that makes it more clear what is happening to the letters, and this seems correct.

Title: Columnar Transposition Cipher

Body:
R, 182 177

Here is the golfed version:

function(t,k){k=unique(unlist(strsplit(tolower(k),"")));t=unlist(strsplit(t,""));l=length(t);c=length(k);r=ceiling(l/c);t=c(t,rep("",c*r-l));cat(matrix(t,r,c)[order(rank(k)),])}

And ungolfed version, which shows how the function takes the data.

# test data
key = "aBeCd"
test = "ABCDEabcdeABCDEabcdeABC!"

# t is the test phrase, k is the key
cipher=function(t,k){
    k=unique(unlist(strsplit(tolower(key),"")))
    t=unlist(strsplit(test,""))
    l=length(t)
    c=length(k)
    r=ceiling(l/c)
    t=c(t,rep("",c*r-l))
    cat(matrix(t,r,c)[order(rank(k)),])
}

# Show that it works
cipher(test,key)
## A B D E C a b d e c A B D E C a b d e c A B !  C

The test cases provided by the OP seem incorrect. I intentionally chose a test case here that makes it more clear what is happening to the letters, and this seems correct.


问:
Write a brain-flak classic interpreter!
Brain-Flak (a cross between Brainf**k and Flak-Overstow) is a stack-based esoteric language. Since this challenge was posted, the language has evolved and updated, but this first revision of the language is known as "brain-flak classic".

You must write a program or function that takes a string of Brain-Flak classic code, and evaluates it. It will also take a (possible empty) list of integers. There are the inputs to the Brain-Flak classic program.

The Language

Brain-Flak has two stacks, known as 'left' and 'right'. The active stack starts at left. If an empty stack is popped or peeked, it will return 0. There are no variables. When the program starts, each input is pushed on to the active stack in order (so that the last input is on top of the stack).

The only valid characters in a Brain-Flak program are ()[]{}<>, and they must always be balanced. If there are invalid characters, or the brackets are unmatched, you get undefined behaviour. Anything is valid.

There are two types of functions: Nilads and Monads. A nilad is a function that takes 0 arguments. Here are all of the nilads:

() +1.

[] -1.

{} Pop the active stack.

<> Toggle the active stack.

These are concatenated together when they are evaluated. So if we had a '3' on top of the active stack, this snippet:

```<code>()(){}
</code>```

would evaluate to 1 + 1 + active.pop() which would evaluate to 5. <> evaluates to 0.

The monads take one argument, a chunk of Brain-Flak code. Here are all of the monads:

(n) Push 'n' on the active stack.

[n] Print 'n' as an int and a newline.

{foo} While active.peek() != 0, do foo. Evaluates to 0¹.

<foo> Execute foo, but evaluate it as 0.

These functions will also return the value inside of them, so

```<code>(()()())
</code>```

Will push 3 and

```<code>[()()()]
</code>```

Will print 3 but

```<code>[(()()())]
</code>```

Will print and push 3.

When the program is done executing, each value left on the active stack is printed as an integer, with a newline between. Values on the other stack are ignored.

Rules:

Your program must support numbers in the (-128, 127) range, and a stack size of at least 255. If you support larger, great.

Underflow/overflow is undefined.

Sample IO:

The empty program:

Input: None

Output: None

Addition. Source:

```<code>({}{})
</code>```

Input:

```<code>2, 3
</code>```

Output:

```<code>5
</code>```

Subtraction. Source:

```<code>({}<>){({}[])<>({}[])<>}<>
</code>```

Input:

```<code>2, 3
</code>```

Output:

```<code>-1
</code>```

Multiplication. Source:

```<code>(()()())
</code>```0

Input:

```<code>(()()())
</code>```1

Output:

```<code>(()()())
</code>```2

Fibonacci. Source:

```<code><>((()))<>{({}[])<>({}<>)<>(({})<>({}<>))<>}<>
</code>```

Input:

```<code>5
</code>```

Output:

```<code>13
8
5
3
2
1
1
</code>```

Truth machine

```<code>{[({})]}
</code>```

Standard loopholes apply, and the shortest answer in bytes wins.

¹: This was actually a mistake on my part. {...} should evaluate to the sum of all of it's runs, which is IMO one of the coolest features of brain-flak. However, for the purposes of this challenge, assume that {...} evaluates as 0.

答:
Python 3, 429 bytes

```<code>import re
S='s+=[v];v=0';T='v+=s.pop()';i=0
d={'()':'v+=1','(':S,')':'a+=[v];'+T,'[]':'v-=1','[':S,']':'print(v);'+T,'<>':'a.reverse()','<':S,'>':T,'{}':'v+=0if a[-1]==""else a.pop()','{':S+';while a[-1]:','}':T}
def r(m):global i;t=m.group();i-=(t=='}');s=' '*i;i+=(t=='{');return''.join(s+r+'\n'for r in d[t].split(';'))
def g(c,*a):
 a,s,v=['']+list(a),[],0;exec(re.sub(r'[<({[]?[]})>]?',r,c));
 while a[-1]!="":print(a.pop())
</code>```

Used like g('[{}{}]', 2, 3)

It uses re.sub to "compile" the brain-flak source to python and then executes the python. (for debuging, replace exec with print to get a listing of the python code)

Properly indenting nested while loops eats up a lot of bytes in the code.

Title: Write a brain-flak classic interpreter!

Body:
Python 3, 429 bytes

import re
S='s+=[v];v=0';T='v+=s.pop()';i=0
d={'()':'v+=1','(':S,')':'a+=[v];'+T,'[]':'v-=1','[':S,']':'print(v);'+T,'<>':'a.reverse()','<':S,'>':T,'{}':'v+=0if a[-1]==""else a.pop()','{':S+';while a[-1]:','}':T}
def r(m):global i;t=m.group();i-=(t=='}');s=' '*i;i+=(t=='{');return''.join(s+r+'\n'for r in d[t].split(';'))
def g(c,*a):
 a,s,v=['']+list(a),[],0;exec(re.sub(r'[<({[]?[]})>]?',r,c));
 while a[-1]!="":print(a.pop())

Used like g('[{}{}]', 2, 3)

It uses re.sub to "compile" the brain-flak source to python and then executes the python. (for debuging, replace exec with print to get a listing of the python code)

Properly indenting nested while loops eats up a lot of bytes in the code.


问:
The rice and chess problem
An Indian legend tells the story of the alleged inventor of the chess game, who impressed the emperor of India with his game so much that he would get rewarded with anything asked.

The man said he wanted to be paid in rice. He wanted a grain of rice for the first square of the chessboard, two for the second, four for the third, eight for the fourth, and so on, until the 64th square.

The emperor was amazed that the man asked for such a small reward, but as his mathematicians started counting, he ended up losing one of his provinces.

Task

Given the length of the side of a hypothetical chessboard (which is 8 on a default chessboard) and the multiplier between squares (which is 2 in the legend), calculate the number of grains of rice the emperor must pay to the man.

Notes

The side length will always be a positive integer. The multiplier could instead be any kind of rational number.

If your language of choice can't display very large numbers, it's okay as long as your program can correctly process smaller inputs.

Also if your language of choice rounds larger values (with exponential notations), it's okay if those values are approximately correct.

Testcases

```<code>Input (side length, multiplier) => Output
8, 2                            => 18446744073709551615
3, 6                            => 2015539
7, 1.5                          => 850161998.2854
5, -3                           => 211822152361
256, 1                          => 65536
2, 2                            => 15
2, -2                           => -5
</code>```

Please note that the explicit formula

```<code>result = (multiplier ^ (side ^ 2) - 1) / (multiplier - 1)
</code>```

Performs wrong on multiplier = 1, as

```<code>1 ^ (side ^ 2) - 1 = 0
1 - 1 = 0
0 / 0 != side ^ 2 (as it should be)
</code>```

Scoring

This is code-golf. Shortest answer in bytes wins.

答:
, 11 chars / 14 bytes

```<code>⨭⩥ î²)ⓜⁿ⁽í$
</code>```

Try it here (Firefox/WebKit Nightly only).

Yes,  now works in WebKit Nightly! Chrome support is next.

Explanation

```<code>⨭⩥ î²)ⓜⁿ⁽í$ // implicit: î = input1, í = input2
   ⩥ î²)       // generate a range [0..î^2)
                     ⓜ      // map over range ($ is mapitem):
        ⁿ⁽í$  //   í^$
⨭            // sum resulting range
              // implicit output
</code>```

Title: The rice and chess problem

Body:
, 11 chars / 14 bytes

⨭⩥ î²)ⓜⁿ⁽í$

Try it here (Firefox/WebKit Nightly only).

Yes,  now works in WebKit Nightly! Chrome support is next.

Explanation

⨭⩥ î²)ⓜⁿ⁽í$ // implicit: î = input1, í = input2
   ⩥ î²)       // generate a range [0..î^2)
                     ⓜ      // map over range ($ is mapitem):
        ⁿ⁽í$  //   í^$
⨭            // sum resulting range
              // implicit output


答:
RETURN, 32 bytes

```<code>[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!
</code>```

Try it here.

Anonymous lambda that leaves result on Stack2. Usage:

```<code>8 2[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!
</code>```

Explanation

```<code>[                              ]!  lambda
 a:                                store multiplier to a
   2^                              square side-length
     0\␊                           create range [0..result)
        {                          set current stack to range
         [  ][     ]#              while loop
          $¥                         check if TOS is truthy
              a;\^␌                  if so, push a^TOS to Stack2
                     ␁            set current stack to Stack2
                       [¤¥][+]#    sum Stack2
</code>```

Title: The rice and chess problem

Body:
An Indian legend tells the story of the alleged inventor of the chess game, who impressed the emperor of India with his game so much that he would get rewarded with anything asked.

The man said he wanted to be paid in rice. He wanted a grain of rice for the first square of the chessboard, two for the second, four for the third, eight for the fourth, and so on, until the 64th square.

The emperor was amazed that the man asked for such a small reward, but as his mathematicians started counting, he ended up losing one of his provinces.

Task

Given the length of the side of a hypothetical chessboard (which is 8 on a default chessboard) and the multiplier between squares (which is 2 in the legend), calculate the number of grains of rice the emperor must pay to the man.

Notes

The side length will always be a positive integer. The multiplier could instead be any kind of rational number.

If your language of choice can't display very large numbers, it's okay as long as your program can correctly process smaller inputs.

Also if your language of choice rounds larger values (with exponential notations), it's okay if those values are approximately correct.

Testcases

```<code>Input (side length, multiplier) => Output
8, 2                            => 18446744073709551615
3, 6                            => 2015539
7, 1.5                          => 850161998.2854
5, -3                           => 211822152361
256, 1                          => 65536
2, 2                            => 15
2, -2                           => -5
</code>```

Please note that the explicit formula

```<code>result = (multiplier ^ (side ^ 2) - 1) / (multiplier - 1)
</code>```

Performs wrong on multiplier = 1, as

```<code>1 ^ (side ^ 2) - 1 = 0
1 - 1 = 0
0 / 0 != side ^ 2 (as it should be)
</code>```

Scoring

This is code-golf. Shortest answer in bytes wins.

Body:
RETURN, 32 bytes

[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

Try it here.

Anonymous lambda that leaves result on Stack2. Usage:

8 2[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

Explanation

[                              ]!  lambda
 a:                                store multiplier to a
   2^                              square side-length
     0\␊                           create range [0..result)
        {                          set current stack to range
         [  ][     ]#              while loop
          $¥                         check if TOS is truthy
              a;\^␌                  if so, push a^TOS to Stack2
                     ␁            set current stack to Stack2
                       [¤¥][+]#    sum Stack2


答:
Actually, 9 bytes

```<code>╗²r`╜ⁿ`MΣ
</code>```

Takes input as side length first, then multiplier.

Try it online!

Explanation:

```<code>╗²r`╜ⁿ`MΣ
╗          save m to reg0
 ²r        range(s**2) ([0, s**2-1])
   `  `M   map (for n in list):
    ╜ⁿ       m**n (m is pushed from reg0)
        Σ  sum
</code>```

Title: The rice and chess problem

Body:
Actually, 9 bytes

╗²r`╜ⁿ`MΣ

Takes input as side length first, then multiplier.

Try it online!

Explanation:

╗²r`╜ⁿ`MΣ
╗          save m to reg0
 ²r        range(s**2) ([0, s**2-1])
   `  `M   map (for n in list):
    ╜ⁿ       m**n (m is pushed from reg0)
        Σ  sum


问:
Write a program whose nontermination is independent of Peano arithmetic

Challenge

Write a program P, taking no input, such that the proposition “the execution of P eventually terminates” is independent of Peano arithmetic.

Formal rules

(In case you are a mathematical logician who thinks the above description is too informal.)

One can, in principle, convert some Universal Turing machine U (e.g. your favorite programming language) into a Peano arithmetic formula HALT over the variable p, where HALT(p) encodes the proposition “U terminates on the program (Gödel-encoded by) p”.  The challenge is to find p such that neither HALT(p) nor ¬HALT(p) can be proven in Peano arithmetic.

You may assume your program runs on an ideal machine with unlimited memory and integers/pointers big enough to access it.

Example

To see that such programs exist, one example is a program that exhaustively searches for a Peano arithmetic proof of 0 = 1.  Peano arithmetic proves that this program halts if and only if Peano arithmetic is inconsistent.  Since Peano arithmetic is consistent but cannot prove its own consistency, it cannot decide whether this program halts.

However, there are many other propositions independent of Peano arithmetic on which you could base your program.

Motivation

This challenge was inspired by a new paper by Yedidia and Aaronson (2016) exhibiting a 7,918-state Turing machine whose nontermination is independent of ZFC, a much stronger system than Peano arithmetic.  You may be interested in its citation [22].  For this challenge, of course, you may use your programming language of choice in place of actual Turing machines.

答:
Haskell, 838 bytes

“If you want something done, …”

import Control.Monad.State
data T=V Int|T:$T|A(T->T)
g=guard
r=runStateT
s!a@(V i)=maybe a id$lookup i s
s!(a:$b)=(s!a):$(s!b)
s@((i,_):_)!A f=A(\a->((i+1,a):s)!f(V$i+1))
c l=do(m,k)<-(`divMod`sum(1<$l)).pred<$>get;g$m>=0;put m;l!!fromEnum k
i&a=V i:$a
i%t=(:$).(i&)<$>t<*>t
x i=c$[4%x i,5%x i,(6&)<$>x i]++map(pure.V)[7..i-1]
y i=c[A<$>z i,1%y i,(2&)<$>y i,3%x i]
z i=(\a e->[(i,e)]!a)<$>y(i+1)
(i?h)p=c[g$any(p#i)h,do q<-y i;i?h$q;i?h$1&q:$p,do f<-z i;a<-x i;g$p#i$f a;c[i?h$A f,do b<-x i;i?h$3&b:$a;i?h$f b],case p of A f->c[(i+1)?h$f$V i,do i?h$f$V 7;(i+1)?(f(V i):h)$f$6&V i];V 1:$q:$r->c[i?(q:h)$r,i?(2&r:h)$V 2:$q];_->mzero]
(V a#i)(V b)=a==b
((a:$b)#i)(c:$d)=(a#i)c&&(b#i)d
(A f#i)(A g)=f(V i)#(i+1)$g$V i
(_#_)_=0<0
main=print$(r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$3&V 7:$(6&V 7))=<<[0..])!!0
```

<h2>Explanation</h2>

<p>This program directly searches for a Peano arithmetic proof of 0 = 1.  Since PA is consistent, this program never terminates; but since PA cannot prove its own consistency, the nontermination of this program is independent of PA.</p>

<p><code>T</code> is the type of expressions and propositions:</p>

<ul>
<li><code>A P</code> represents the proposition ∀<em>x</em> [<em>P</em>(<em>x</em>)].</li>
<li><code>(V 1 :$ P) :$ Q</code> represents the proposition <em>P</em> → <em>Q</em>.</li>
<li><code>V 2 :$ P</code> represents the proposition ¬<em>P</em>.</li>
<li><code>(V 3 :$ x) :$ y</code> represents the proposition <em>x</em> = <em>y</em>.</li>
<li><code>(V 4 :$ x) :$ y</code> represents the natural <em>x</em> + <em>y</em>.</li>
<li><code>(V 5 :$ x) :$ y</code> represents the natural <em>x</em> ⋅ <em>y</em>.</li>
<li><code>V 6 :$ x</code> represents the natural S(<em>x</em>) = <em>x</em> + 1.</li>
<li><code>V 7</code> reprents the natural 0.</li>
</ul>

<p>In an environment with <em>i</em> free variables, we encode expressions, propositions, and proofs as 2×2 integer matrices [1, 0; <em>a</em>, <em>b</em>], as follows:</p>

<ul>
<li>M(<em>i</em>, ∀<em>x</em> [<em>P</em>(<em>x</em>)]) = [1, 0; 1, 4] ⋅ M(<em>i</em>, λ<em>x</em> [P(x)])</li>
<li>M(<em>i</em>, λ<em>x</em> [<em>F</em>(<em>x</em>)]) = M(<em>i</em> + 1, <em>F</em>(<em>x</em>)) where M(<em>j</em>, <em>x</em>) = [1, 0; 5 + <em>i</em>, 4 + <em>j</em>] for all <em>j</em> > <em>i</em></li>
<li>M(<em>i</em>, <em>P</em> → <em>Q</em>) = [1, 0; 2, 4] ⋅ M(<em>i</em>, <em>P</em>) ⋅ M(<em>i</em>, <em>Q</em>)</li>
<li>M(<em>i</em>, ¬<em>P</em>) = [1, 0; 3, 4] ⋅ M(<em>i</em>, <em>P</em>)</li>
<li>M(<em>i</em>, <em>x</em> = <em>y</em>) = [1, 0; 4, 4] ⋅ M(<em>i</em>, <em>x</em>) ⋅ M(<em>i</em>, <em>y</em>)</li>
<li>M(<em>i</em>, <em>x</em> + <em>y</em>) = [1, 0; 1, 4 + <em>i</em>] ⋅ M(<em>i</em>, <em>x</em>) ⋅ M(<em>i</em>, <em>y</em>)</li>
<li>M(<em>i</em>, <em>x</em> ⋅ <em>y</em>) = [1, 0; 2, 4 + <em>i</em>] ⋅ M(<em>i</em>, <em>x</em>) ⋅ M(<em>i</em>, <em>y</em>)</li>
<li>M(<em>i</em>, S <em>x</em>) = [1, 0; 3, 4 + <em>i</em>] ⋅ M(<em>i</em>, <em>x</em>)</li>
<li>M(<em>i</em>, 0) = [1, 0; 4, 4 + <em>i</em>]</li>
<li>M(<em>i</em>, (<em>Γ</em>, <em>P</em>) ⊢ <em>P</em>) = [1, 0; 1, 4]</li>
<li>M(<em>i</em>, <em>Γ</em> ⊢ <em>P</em>) = [1, 0; 2, 4] ⋅ M(<em>i</em>, <em>Q</em>) ⋅ M(<em>i</em>, <em>Γ</em> ⊢ <em>Q</em>) ⋅ M(<em>i</em>, <em>Γ</em> ⊢ <em>Q</em> → <em>P</em>)</li>
<li>M(<em>i</em>, <em>Γ</em> ⊢ <em>P</em>(<em>x</em>)) = [1, 0; 3, 4] ⋅ M(<em>i</em>, λ<em>x</em> [P(x)]) ⋅ M(<em>i</em>, <em>x</em>) ⋅ [1, 0; 1, 2] ⋅ M(<em>i</em>, <em>Γ</em> ⊢ ∀<em>x</em> P(x))</li>
<li>M(<em>i</em>, <em>Γ</em> ⊢ <em>P</em>(<em>x</em>)) = [1, 0; 3, 4] ⋅ M(<em>i</em>, λ<em>x</em> [P(x)]) ⋅ M(<em>i</em>, <em>x</em>) ⋅ [1, 0; 2, 2] ⋅ M(<em>i</em>, <em>y</em>) ⋅ M(<em>i</em>, <em>Γ</em> ⊢ <em>y</em> = <em>x</em>) ⋅ M(<em>i</em>, <em>Γ</em> ⊢ <em>P</em>(<em>y</em>))</li>
<li>M(<em>i</em>, <em>Γ</em> ⊢ ∀<em>x</em>, <em>P</em>(<em>x</em>)) = [1, 0; 8, 8] ⋅ M(<em>i</em>, λ<em>x</em> [<em>Γ</em> ⊢ <em>P</em>(<em>x</em>)])</li>
<li>M(<em>i</em>, <em>Γ</em> ⊢ ∀<em>x</em>, <em>P</em>(<em>x</em>)) = [1, 0; 12, 8] ⋅ M(<em>i</em>, <em>Γ</em> ⊢ <em>P</em>(0)) ⋅ M(<em>i</em>, λ<em>x</em> [(<em>Γ</em>, <em>P</em>(<em>x</em>)) ⊢ <em>P</em>(S(<em>x</em>))])</li>
<li>M(<em>i</em>, <em>Γ</em> ⊢ <em>P</em> → <em>Q</em>) = [1, 0; 8, 8] ⋅ M(<em>i</em>, (<em>Γ</em>, <em>P</em>) ⊢ <em>Q</em>)</li>
<li>M(<em>i</em>, <em>Γ</em> ⊢ <em>P</em> → <em>Q</em>) = [1, 0; 12, 8] ⋅ M(<em>i</em>, (<em>Γ</em>, ¬<em>Q</em>) ⊢ ¬<em>P</em>)</li>
</ul>

<p>The remaining axioms are encoded numerically and included in the initial environment <em>Γ</em>:</p>

<ul>
<li>M(0, ∀<em>x</em> [<em>x</em> = <em>x</em>]) = [1, 0; 497, 400]</li>
<li>M(0, ∀<em>x</em> [¬(S(<em>x</em>) = 0)]) = [1, 0; 8269, 8000]</li>
<li>M(0, ∀<em>x</em> ∀<em>y</em> [S(<em>x</em>) = S(<em>y</em>) → <em>x</em> = <em>y</em>]) = [1, 0; 56106533, 47775744]</li>
<li>M(0, ∀<em>x</em> [<em>x</em> + 0 = <em>x</em>]) = [1, 0; 12033, 10000]</li>
<li>M(0, ∀<em>y</em> [<em>x</em> + S(<em>y</em>) = S(<em>x</em> + <em>y</em>)]) = [1, 0; 123263749, 107495424]</li>
<li>M(0, ∀<em>x</em> [<em>x</em> ⋅ 0 = 0]) = [1, 0; 10049, 10000]</li>
<li>M(0, ∀<em>x</em> ∀<em>y</em> [<em>x</em> ⋅ S(<em>y</em>) = <em>x</em> ⋅ <em>y</em> + <em>x</em>]) = [1, 0; 661072709, 644972544]</li>
</ul>

<p>A proof with matrix [1, 0; <em>a</em>, <em>b</em>] can be checked given only the lower-left corner <em>a</em> (or any other value congruent to <em>a</em> modulo <em>b</em>); the other values are there to enable composition of proofs.</p>

<p>For example, here is a proof that addition is commutative.</p>

<ul>
<li>M(0, <em>Γ</em> ⊢ ∀<em>x</em> ∀<em>y</em> [<em>x</em> + <em>y</em> = <em>y</em> + <em>x</em>]) = [1, 0; 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644, 14010499234317302152403198529613715336094817740448888109376168978138227692104106788277363562889534501599380268163213618740021570705080096139804941973102814335632180523847407060058534443254569282138051511292576687428837652027900127452656255880653718107444964680660904752950049505280000000000000000000000000000000000000000000000000000000]</li>
</ul>

<p>You can verify it with the program as follows:</p>

```*Main> let p = A $ \x -> A $ \y -> V 3 :$ (V 4 :$ x :$ y) :$ (V 4 :$ y :$ x)
*Main> let a = 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644
*Main> r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$p)a :: [((),Integer)]
[((),0)]
```

If the proof were invalid you would get the empty list instead.

Body:
Haskell, 838 bytes

“If you want something done, …”

import Control.Monad.State
data T=V Int|T:$T|A(T->T)
g=guard
r=runStateT
s!a@(V i)=maybe a id$lookup i s
s!(a:$b)=(s!a):$(s!b)
s@((i,_):_)!A f=A(\a->((i+1,a):s)!f(V$i+1))
c l=do(m,k)<-(`divMod`sum(1<$l)).pred<$>get;g$m>=0;put m;l!!fromEnum k
i&a=V i:$a
i%t=(:$).(i&)<$>t<*>t
x i=c$[4%x i,5%x i,(6&)<$>x i]++map(pure.V)[7..i-1]
y i=c[A<$>z i,1%y i,(2&)<$>y i,3%x i]
z i=(\a e->[(i,e)]!a)<$>y(i+1)
(i?h)p=c[g$any(p#i)h,do q<-y i;i?h$q;i?h$1&q:$p,do f<-z i;a<-x i;g$p#i$f a;c[i?h$A f,do b<-x i;i?h$3&b:$a;i?h$f b],case p of A f->c[(i+1)?h$f$V i,do i?h$f$V 7;(i+1)?(f(V i):h)$f$6&V i];V 1:$q:$r->c[i?(q:h)$r,i?(2&r:h)$V 2:$q];_->mzero]
(V a#i)(V b)=a==b
((a:$b)#i)(c:$d)=(a#i)c&&(b#i)d
(A f#i)(A g)=f(V i)#(i+1)$g$V i
(_#_)_=0<0
main=print$(r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$3&V 7:$(6&V 7))=<<[0..])!!0

Explanation

This program directly searches for a Peano arithmetic proof of 0 = 1.  Since PA is consistent, this program never terminates; but since PA cannot prove its own consistency, the nontermination of this program is independent of PA.

T is the type of expressions and propositions:

A P represents the proposition ∀x [P(x)].

(V 1 :$ P) :$ Q represents the proposition P → Q.

V 2 :$ P represents the proposition ¬P.

(V 3 :$ x) :$ y represents the proposition x = y.

(V 4 :$ x) :$ y represents the natural x + y.

(V 5 :$ x) :$ y represents the natural x ⋅ y.

V 6 :$ x represents the natural S(x) = x + 1.

V 7 reprents the natural 0.

In an environment with i free variables, we encode expressions, propositions, and proofs as 2×2 integer matrices [1, 0; a, b], as follows:

M(i, ∀x [P(x)]) = [1, 0; 1, 4] ⋅ M(i, λx [P(x)])

M(i, λx [F(x)]) = M(i + 1, F(x)) where M(j, x) = [1, 0; 5 + i, 4 + j] for all j > i

M(i, P → Q) = [1, 0; 2, 4] ⋅ M(i, P) ⋅ M(i, Q)

M(i, ¬P) = [1, 0; 3, 4] ⋅ M(i, P)

M(i, x = y) = [1, 0; 4, 4] ⋅ M(i, x) ⋅ M(i, y)

M(i, x + y) = [1, 0; 1, 4 + i] ⋅ M(i, x) ⋅ M(i, y)

M(i, x ⋅ y) = [1, 0; 2, 4 + i] ⋅ M(i, x) ⋅ M(i, y)

M(i, S x) = [1, 0; 3, 4 + i] ⋅ M(i, x)

M(i, 0) = [1, 0; 4, 4 + i]

M(i, (Γ, P) ⊢ P) = [1, 0; 1, 4]

M(i, Γ ⊢ P) = [1, 0; 2, 4] ⋅ M(i, Q) ⋅ M(i, Γ ⊢ Q) ⋅ M(i, Γ ⊢ Q → P)

M(i, Γ ⊢ P(x)) = [1, 0; 3, 4] ⋅ M(i, λx [P(x)]) ⋅ M(i, x) ⋅ [1, 0; 1, 2] ⋅ M(i, Γ ⊢ ∀x P(x))

M(i, Γ ⊢ P(x)) = [1, 0; 3, 4] ⋅ M(i, λx [P(x)]) ⋅ M(i, x) ⋅ [1, 0; 2, 2] ⋅ M(i, y) ⋅ M(i, Γ ⊢ y = x) ⋅ M(i, Γ ⊢ P(y))

M(i, Γ ⊢ ∀x, P(x)) = [1, 0; 8, 8] ⋅ M(i, λx [Γ ⊢ P(x)])

M(i, Γ ⊢ ∀x, P(x)) = [1, 0; 12, 8] ⋅ M(i, Γ ⊢ P(0)) ⋅ M(i, λx [(Γ, P(x)) ⊢ P(S(x))])

M(i, Γ ⊢ P → Q) = [1, 0; 8, 8] ⋅ M(i, (Γ, P) ⊢ Q)

M(i, Γ ⊢ P → Q) = [1, 0; 12, 8] ⋅ M(i, (Γ, ¬Q) ⊢ ¬P)

The remaining axioms are encoded numerically and included in the initial environment Γ:

M(0, ∀x [x = x]) = [1, 0; 497, 400]

M(0, ∀x [¬(S(x) = 0)]) = [1, 0; 8269, 8000]

M(0, ∀x ∀y [S(x) = S(y) → x = y]) = [1, 0; 56106533, 47775744]

M(0, ∀x [x + 0 = x]) = [1, 0; 12033, 10000]

M(0, ∀y [x + S(y) = S(x + y)]) = [1, 0; 123263749, 107495424]

M(0, ∀x [x ⋅ 0 = 0]) = [1, 0; 10049, 10000]

M(0, ∀x ∀y [x ⋅ S(y) = x ⋅ y + x]) = [1, 0; 661072709, 644972544]

A proof with matrix [1, 0; a, b] can be checked given only the lower-left corner a (or any other value congruent to a modulo b); the other values are there to enable composition of proofs.

For example, here is a proof that addition is commutative.

M(0, Γ ⊢ ∀x ∀y [x + y = y + x]) = [1, 0; 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644, 14010499234317302152403198529613715336094817740448888109376168978138227692104106788277363562889534501599380268163213618740021570705080096139804941973102814335632180523847407060058534443254569282138051511292576687428837652027900127452656255880653718107444964680660904752950049505280000000000000000000000000000000000000000000000000000000]

You can verify it with the program as follows:

*Main> let p = A $ \x -> A $ \y -> V 3 :$ (V 4 :$ x :$ y) :$ (V 4 :$ y :$ x)
*Main> let a = 6651439985424903472274778830412211286042729801174124932726010503641310445578492460637276210966154277204244776748283051731165114392766752978964153601068040044362776324924904132311711526476930755026298356469866717434090029353415862307981531900946916847172554628759434336793920402956876846292776619877110678804972343426850350512203833644
*Main> r(8?map fst(r(y 8)=<<[497,8269,56106533,12033,123263749,10049,661072709])$p)a :: [((),Integer)]
[((),0)]

If the proof were invalid you would get the empty list instead.


问:
Jordan Decomposition
Important note: Because this challenge only applies to square matrices, any time I use the term "matrix", it is assumed that I am referring to a square matrix. I am leaving off the "square" description for brevity's sake.

Background

Many matrix-related operations, such as computing the determinant, solving a linear system, or extending scalar-valued functions to matrices are made easier by using a diagonal matrix (one whose elements that are not on the main diagonal are 0) that is similar to the original matrix (meaning, for the input matrix A and the diagonal matrix D, there exists some invertible matrix P such that D = P^(-1) * A * P; also, D and A share some important properties, like eigenvalues, determinant, and trace). For matrices with distinct eigenvalues (the roots to the matrix's characteristic polynomial, given by solving det(A-λI) = 0 for λ, where I is the identity matrix with the same dimensions as A), diagonalization is simple: D is a matrix with the eigenvalues on the main diagonal, and P is a matrix formed from eigenvectors corresponding to those eigenvalues (in the same order). This process is called eigendecomposition.

However, matrices with repeated eigenvalues cannot be diagonalized in this manner. Luckily, the Jordan normal form of any matrix can be computed rather easily, and is not much harder to work with than a regular diagonal matrix. It also has the nice property that, if the eigenvalues are unique, then Jordan decomposition is identical to eigendecomposition.

Jordan decomposition explained

For a square matrix A whose eigenvalues all have a geometric multiplicity of 1, the process of Jordan decomposition can be described as such:

Let λ = {λ_1, λ_2, ... λ_n} be the list of eigenvalues of A, with multiplicity, with repeated eigenvalues appearing consecutively.

Create a diagonal matrix J whose elements are the elements of λ, in the same order.

For each eigenvalue with multiplicity greater than 1, place a 1 to the right of each of the repetitions of the eigenvalue in the main diagonal of J, except the last.

The resulting matrix J is a Jordan normal form of A (there can be multiple Jordan normal forms for a given matrix, depending on the order of the eigenvalues).

A worked example

Let A be the following matrix:

The eigenvalues of A, with multiplicity, are λ = {1, 2, 4, 4}. By putting these into a diagonal matrix, we get this result:

Next, we place 1s to the right of all but one of each of the repeated eigenvalues. Since 4 is the only repeated eigenvalue, we place a single 1 next to the first 4:

This is a Jordan normal form of A (a single matrix can potentially have several valid Jordan normal forms, but I'm glossing over that detail for the purpose of explanation).

The task

Given a square matrix A as input, output a valid Jordan normal form of A.

The input and output may be in any reasonable format (2D array/list/whatever, list/array/whatever of column or row vectors, a builtin matrix data type, etc.).

The elements and eigenvalues of A will always be integers in the range [-200, 200].

For the sake of simplicity, all of the eigenvalues will have a geometric multiplicity of 1 (and thus the above process holds).

A will at most be a 10x10 matrix and at least a 2x2 matrix.

Builtins that compute eigenvalues and/or eigenvectors or perform eigendecomposition, Jordan decomposition, or any other kind of decomposition/diagonalization are not allowed. Matrix arithmetic, matrix inversion, and other matrix builtins are allowed.

Test cases

```<code>[[1, 0], [0, 1]] -> [[1, 1], [0, 1]]
[[3, 0], [0, 3]] -> [[1, 1], [0, 1]]
[[4, 2, 2], [1, 2, 2],[0, 3, 3]] -> [[6, 0, 0], [0, 3, 0], [0, 0, 0]]
[[42, 48, 40, 64, 64], [41, 47, 31, 58, 42], [-55, -47, -27, -74, -46], [-46, -58, -46, -70, -68], [30, 20, 12, 34, 18]] -> [[10, 0, 0, 0, 0], [0, -18, 0, 0, 0], [0, 0, 6, 1, 0], [0, 0, 0, 6, 1], [0, 0, 0, 0, 6]]
</code>```

答:
Sage, 79 bytes

lambda A:block_diagonal_matrix([jordan_block(*r)for r in A.charpoly().roots()])
```

Try it online

Since nobody else is posting solutions, I might as well go ahead and post one.

A.charpoly.roots() computes the roots (and algebraic multiplicities) of the characteristic polynomial of A (aka the eigenvalues and multiplicities). jordan_block constructs a Jordan block from the given root and multiplicity. block_diagonal_matrix forms a matrix with the Jordan blocks on the diagonal, which is exactly the definition of a Jordan normal form.

Title: Jordan Decomposition

Body:
Sage, 79 bytes

lambda A:block_diagonal_matrix([jordan_block(*r)for r in A.charpoly().roots()])

Try it online

Since nobody else is posting solutions, I might as well go ahead and post one.

A.charpoly.roots() computes the roots (and algebraic multiplicities) of the characteristic polynomial of A (aka the eigenvalues and multiplicities). jordan_block constructs a Jordan block from the given root and multiplicity. block_diagonal_matrix forms a matrix with the Jordan blocks on the diagonal, which is exactly the definition of a Jordan normal form.


问:
How many steps does it take from n to 1 by subtracting the greatest divisor?
Inspired by this question over at Mathematics.

The Problem

Let n be a natural number ≥ 2. Take the biggest divisor of n – which is different from n itself – and subtract it from n. Repeat until you get 1.

The Question

How many steps does it take to reach 1 for a given number n ≥ 2.

Detailed Example

Let n = 30.

The greatest divisor of:

```<code>1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1
</code>```

It takes 6 steps to reach 1.

Input

Input is an integer n, where n ≥ 2.

Your program should support input up to the language's maximum integer value.

Output

Simply output the number of steps, like 6.

Leading/trailing whitespaces or newlines are fine.

Examples

```<code>f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015
</code>```

Requirements

You can get input from STDIN, command line arguments, as function parameters or from the closest equivalent.

You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.

This is code-golf so shortest answer in bytes wins.

Standard loopholes are disallowed.

This series can be found on OEIS as well: A064097

A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.

答:
Jelly, 9 bytes

```<code>ÆṪÐĿÆFL€S
</code>```

Try it online! or verify all test cases.

Background

The definition of sequence A064097 implies that

$$\small{a(p)-a(p-1)=1}\text{ for all primes }p\text{ and }a(km)=a(k)+a(m)\text{ for all }k,m\in \mathbb{N}$$

By Euler's product formula

$$\small{\varphi(n)=n\prod_{p|n}\left(1-{1\over p}\right)=n\prod_{p|n}{{p-1}\over p}}$$

where \$\varphi\$ denotes Euler's totient function and \$p\$ varies only over prime numbers.

Combining both, we deduce the property

$$\small{a(\varphi(n))=a\left(n\prod_{p|n}{{p-1}\over p}\right)=a(n)+\sum_{p|n}\left(a(p-1)-a(p)\right)=a(n)-\sum_{p|n}{1=a(n)-\omega(n)}}$$

where \$\omega\$ denotes the number of distinct prime factors of \$n\$.

Applying the resulting formula \$k + 1\$ times, where \$k\$ is large enough so that \$\varphi^{k+1}(n)=1\$, we get

$$\small{
\begin{aligned}
0=a\left(\varphi^{k+1}(n)\right)=a\left(\varphi^k(n)\right)-\omega\left(\varphi^k(n)\right)&=a\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^k(n)\right) \\
&= \cdots = a(n)-\sum_{j=0}^k\omega\left(\varphi^j(n)\right)
\end{aligned}
}$$

From this property, we obtain the formula

$$\small{a(n)=\sum_{j=0}^k\omega\left(\varphi^j(n)\right)=\sum_{j=0}^{+\infty}\omega\left(\varphi^j(n)\right)}$$

where the last equality holds because \$\omega(1)=0\$.

How it works

```<code>ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.
</code>```

Body:
Jelly, 9 bytes

ÆṪÐĿÆFL€S

<a href="http://jelly.tryitonline.net/#code=w4bhuarDkMS_w4ZGTOKCrFM&input=&args=MTU3MDQ3NzgxMTY1NzIzNzIxNzAzODQxMTUyMDYyMDM3MDQ1Nzc0MTQzMTkxNzExNTg0NDExOTM0MDg2MDgzNjM2NzA3Njc5NTM1MDgwMjQwMTY3Njg5MzM2ODk2OTkxMjExMjMyOTk3OTU5NjUzMzYxODIxNTI3MzA2OTYxODU4NjA5NTY3NjIyMjg5ODg4ODA2NTA1NTYyNTgzOTgzOTI5MDk1NDMyMTU3MzMwMjc1MzI5ODE2MzA3NzYxMzc4NTM4ODExMTY4MzgwNDIxNzY3NjMxMDk0NTcwMDAwNjQxMzY4MDE1NTgwMTcyNjc0MzQxNTkxMzY3Mzc4NTAxODE4OTM5NzIwMTA3OTk1NjE0MDE3MTgyNjg5MjIwOTQ2MTk0ODg0NzM0MTI1MjU0Mzk1MzE5NzQ0MDUyMDQyMDU4NDE5Njk0MzA1MTUwNTIyNzg3NzYwNDU4NjY0OTQ5NTIzNzc4OTYxMTA5MjQxNzUwOTg3NjA5OTkzNTc5NjE0NjU4NDk5MTE5ODczNzgyOTAxODYxNjg5MjU2ODYzODM4MTM2NjkyMTEwMTY5MTc0OTI0OTMxNTU5MTQ0MDE2NDE0MTU5MzU5NjYyNzUyMDIyNjU0Mzk5NjcyODM0NjEzNDU1MzMwMDg3OTIwMzQyNTg1NTM5NjU5NDMyOTg0NTc2" rel="nofollow noreferrer">Try it online! or <a href="http://jelly.tryitonline.net/#code=w4bhuarDkMS_w4ZGTOKCrFMKw4figqxH&input=&args=NSwgMzAsIDMxLCAzMiwgMTAwLCAyMDAsIDE1NzA0Nzc4MTE2NTcyMzcyMTcwMzg0MTE1MjA2MjAzNzA0NTc3NDE0MzE5MTcxMTU4NDQxMTkzNDA4NjA4MzYzNjcwNzY3OTUzNTA4MDI0MDE2NzY4OTMzNjg5Njk5MTIxMTIzMjk5Nzk1OTY1MzM2MTgyMTUyNzMwNjk2MTg1ODYwOTU2NzYyMjI4OTg4ODgwNjUwNTU2MjU4Mzk4MzkyOTA5NTQzMjE1NzMzMDI3NTMyOTgxNjMwNzc2MTM3ODUzODgxMTE2ODM4MDQyMTc2NzYzMTA5NDU3MDAwMDY0MTM2ODAxNTU4MDE3MjY3NDM0MTU5MTM2NzM3ODUwMTgxODkzOTcyMDEwNzk5NTYxNDAxNzE4MjY4OTIyMDk0NjE5NDg4NDczNDEyNTI1NDM5NTMxOTc0NDA1MjA0MjA1ODQxOTY5NDMwNTE1MDUyMjc4Nzc2MDQ1ODY2NDk0OTUyMzc3ODk2MTEwOTI0MTc1MDk4NzYwOTk5MzU3OTYxNDY1ODQ5OTExOTg3Mzc4MjkwMTg2MTY4OTI1Njg2MzgzODEzNjY5MjExMDE2OTE3NDkyNDkzMTU1OTE0NDAxNjQxNDE1OTM1OTY2Mjc1MjAyMjY1NDM5OTY3MjgzNDYxMzQ1NTMzMDA4NzkyMDM0MjU4NTUzOTY1OTQzMjk4NDU3Ng" rel="nofollow noreferrer">verify all test cases.

Background

The definition of sequence A064097 implies that

$$\small{a(p)-a(p-1)=1}\text{ for all primes }p\text{ and }a(km)=a(k)+a(m)\text{ for all }k,m\in \mathbb{N}$$

By Euler's product formula

$$\small{\varphi(n)=n\prod_{p|n}\left(1-{1\over p}\right)=n\prod_{p|n}{{p-1}\over p}}$$

where \$\varphi\$ denotes Euler's totient function and \$p\$ varies only over prime numbers.

Combining both, we deduce the property

$$\small{a(\varphi(n))=a\left(n\prod_{p|n}{{p-1}\over p}\right)=a(n)+\sum_{p|n}\left(a(p-1)-a(p)\right)=a(n)-\sum_{p|n}{1=a(n)-\omega(n)}}$$

where \$\omega\$ denotes the number of distinct prime factors of \$n\$.

Applying the resulting formula \$k + 1\$ times, where \$k\$ is large enough so that \$\varphi^{k+1}(n)=1\$, we get

$$\small{
\begin{aligned}
0=a\left(\varphi^{k+1}(n)\right)=a\left(\varphi^k(n)\right)-\omega\left(\varphi^k(n)\right)&=a\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^k(n)\right) \\
&= \cdots = a(n)-\sum_{j=0}^k\omega\left(\varphi^j(n)\right)
\end{aligned}
}$$

From this property, we obtain the formula

$$\small{a(n)=\sum_{j=0}^k\omega\left(\varphi^j(n)\right)=\sum_{j=0}^{+\infty}\omega\left(\varphi^j(n)\right)}$$

where the last equality holds because \$\omega(1)=0\$.

How it works

ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.

ContentLicense: CC BY-SA 4.0