Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- KX Community
- :
- Discussion Forums
- :
- kdb+ and q
- :
- Project Euler #4

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Project Euler #4

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.23 12:15 PM

*We find the highest palindromic number in a list, and discover a general form for the last (or first) item that passes a test, without testing every item. *

https://projecteuler.net/problem=4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009=91×99. Find the largest palindrome made from the product of two 3-digit numbers.

Our candidates are the products of the unique pairs of 3-digit numbers:

```
c:prd each distinct asc each {x cross x} 1 _ til 1000 / candidate products
ip:{x~reverse x} / is palindrome?
max c where ip each string c
```

Or we can loop through the products in descending order:

```
i:count C:asc c
while[not ip string C i-:1;]
C i
```

The cost of the sort and the explicit loop is repaid by not casting the entire list to strings and testing all of them.

```
q)\ts max c where ip each string c
94 24835552
q)\ts i:count C:asc c; while[not ip string C i-:1;]; C i
10 12584304
```

A functional version of the above:

`.[@] ({not ip string x y}.) @[;1;-1+]/ (asc c;count[c]-1)`

Note the use of `@[;1;-1+]/`

to decrement the index, and `.[@]`

to resolve the result.

From this we can see a general form for finding the last item that passes a test:

```
lastitem:{[test;list].[@] ({x y z}[test].) @[;1;-1+]/ (list;-1+count list)}
lastitem[not ip string@] asc c
```

From https://github.com/qbists/studyq/blob/main/euler/04.md

Studying q rocks. 😂

1 REPLY 1

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

2022.10.26 11:48 AM

Brilliant post @SJT,

Great reference for our KX Community!

Main Office Contacts

**EMEA**

Tel: +44 (0)28 3025 2242

**AMERICAS**

Tel: +1 (212) 447 6700

**APAC**

Tel: +61 (0)2 9236 5700

Useful Information

Resources

KX. All Rights Reserved.

KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.